Codeforces #236 Div1. D. Beautiful Pairs of Numbers

Div1Dの割に正答者が多い問題。
http://codeforces.com/contest/403/problem/D

問題

パラメータNと、(A[i],B[i])の整数対K個からなる数列を考える。
これらは以下の関係にある。

• 1≦A[1]
• A[i]≦B[i]
• B[i]＜A[i+1]
• B[k]≦N
• B[i]-A[i]=C[i]とすると、Cの各要素はdistinctである。

N,Kの対がK個与えられる。
N,Kに対し条件を満たす数列が何個あるか求めよ。

解法

Nの上限が1000と小さい。
また、Kの上限は1000と一見大きいが、C[i]がdistinctな条件から余り大きなKに対しては求める数列は1つも存在しえない。
実際、Kが50以上のケースは考えなくて良い。

まず、B[i]とA[i+1]の差は無視して、異なる整数の和x個で合計yとなるような整数の組み合わせDP[x][y]を求めよう。
これはO(N^2*K)程度の単純なDPで求めることができる。

各クエリN,Kに対し、C[i]の総和sを0～Nまで総当たりしよう。
するとC[i]の組み合わせはsに対しDP[s][K]となる。
あとは残りN-s個の整数を、1とA[1]の間、B[i]とA[i+1]、B[K]とNの間に挿入する方法を掛ければよい。

ll pat[1005][55];
ll mo=1000000007;
int N,K,T;

ll comb(int P_,int Q_) {
	static const int N_=2020;
	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;
	
	pat[0][0]=1;
	for(i=1;i<=1000;i++) {
		for(x=1000;x>=0;x--) if(x-i>=0) {
			for(y=50;y>=0;y--) if(pat[x-i][y]) pat[x][y+1] = (pat[x][y+1] + pat[x-i][y]*(y+1)) % mo;
		}
	}
	cin>>T;
	while(T--) {
		cin>>N>>K;
		ll ret=0;
		if(K>50) K=50;
		FOR(i,N+1) if(pat[i][K]) ret += pat[i][K] * comb(N-i+K,K) % mo;
		cout<<ret%mo<<endl;
	}
	
}

まとめ

確かにDiv1C位でいい難易度かも？