AtCoder ABC #281 : Ex - Alchemy

こういう分割統治もあるのか…。
https://atcoder.jp/contests/abc281/tasks/abc281_h

問題

初期状態でレベル1の宝石がA種類、それぞれ大量にある。
2以上のレベルnに対し、レベルnの宝石は以下のように既存の宝石から作ることができる。

• レベルn未満の宝石をn個集める。
• 各宝石は異なっていなければならない。
• レベル2以上の宝石は、高々1個しか使えない。

レベルNの宝石の作り方は何通りか。

解法

F(x) := レベル1の宝石の選び方に対応する母関数
とし、とする。
A(n) := レベルnの宝石の作り方 (n≧2)
とする。求めたいのはA(N)となる。この値は以下の通り計算できる。

分割統治法の要領で、A(n)を小さい順に求めつつ、右辺の積を求めて行こう。
右辺の多項式の積を求める際は、以後分割統治の過程で必要な部分だけ絞って行うと良い。

int N;
ll mo;

ll dp[505][505];
ll p2[1202020];
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	dp[1][1]=1;
	p2[0]=1;
	FOR(i,N*N) p2[i+1]=p2[i]*2%mo;
	
	for(i=1;i<=N-2;i++) {
		for(j=1;j<=N;j++) if(dp[i][j]) {
			ll p=p2[j]-1;
			ll kv=dp[i][j];
			for(k=1;i+k<N;k++) {
				kv=(kv*p)%mo;
				(dp[i+k][k]+=kv*comb(N-1-i,k)%mo*p2[k*(k-1)/2])%=mo;
			}
		}
	}
	ll ret=0;
	for(j=1;j<=N;j++) ret+=dp[N-1][j]*(p2[j]-1)%mo;
	cout<<ret%mo<<endl;
	
}

解法

分割統治法による多項式の乗算に関するテク、だいぶ慣れてきたと思ったけどまだまだあるんだな。