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位でいい難易度かも?