블 루 브리지 컵 제9 회 자바 B 팀 - 10 번 문제 - 쌓 인 계수 문제 - 동적 계획
N N 。
。 ， 。
N 1~N， ？
N=4 3 ：
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3
， 1000000009 。
【 】 N。
40% ，1 <= N <= 1000
70% ，1 <= N <= 10000
100% ，1 <= N <= 100000
【 】 。
【 】 4
【 】 3
： （ ） < 256M CPU < 1000ms
， ：“ ...” 。
， ， 。 package 。 jdk1.7 。
：Main， 。사고: d [i] 가 완전 이 진 트 리 i 번 위 치 를 뿌리 노드 로 하 는 이 진 트 리 의 개수 라 고 가정 하면 우 리 는 지금 n 개의 점 을 이 완전 이 진 트 리 에 넣 어야 한다. 분명히 뿌리 노드 가 확정 되 었 고 가장 작은 것 만 넣 을 수 있다. 그 다음 에 왼쪽 트 리 의 노드 개 수 를 lsize 라 고 가정 하면 우 리 는 n - 1 개의 노드 에서 lsize 개의 노드 를 선택 하여 왼쪽 트 리 에 넣 어야 한다.선택 방법 은 모두 조합 수 C (n - 1, lsize) 종 으로 나머지 는 오른쪽 나무 에 놓 기 때문에 d [i] = C (n - 1, lsize) * d [i 의 왼쪽 아들] * d [i 의 오른쪽 아들];
주의: 조합 수 를 구 하려 면 빠 른 멱, 곱셈 역 원 의 지식 이 필요 합 니 다.i 를 뿌리 노드 의 개 수 를 동적 계획 으로 계산 할 수 있 습 니 다. s [i] = s [i 의 왼쪽 아들] + s [i 의 오른쪽 아들];
역 원 O (nlongn), 동적 계획 O (n) 를 구 합 니 다.
따라서 이 알고리즘 은 시간 복잡 도 O (nlongn) 로 본 문제 의 최대 데이터 10 ^ 5 에서 시간 적 타당 성 이 있 습 니 다.
#include
#include
#define _for(i,a,b) for(int i=a;i=b;i--)
#define mset(a,val,n) for(int i=0;i>n;
f[0]=1;
_for(i,1,100005){
f[i]=f[i-1]*i%mod;
inv[i]=qpow(f[i],mod-2);
}
_unfor(i,n,1)
s[i]=(i*2<=n?s[i*2]:0)+((i*2+1)<=n?s[i*2+1]:0)+1; //c[i]<=n
//
mset(d,1,n+5);
_unfor(i,n,1)if(i*2+1<=n)
d[i]= ((C(s[i]-1,s[i*2+1])*d[i*2])%mod*d[i*2+1])%mod;
cout<< d[1]< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정규 표현 식 (python 3)정규 표현 식 은 문자 조작 에 대한 논리 적 공식 으로 미리 정 의 된 특정한 문자 와 특정한 문자 의 조합 으로 '규칙 문자열' 을 구성 하 는 것 입 니 다. match 는 문자열 의 시작 위치 에서 패턴 과 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
