これ系苦手だけど幸いどうにかなった。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_j
問題
N個の色が異なる筒があり、それぞれA[i]個の筒と同じ色のボールが入っている。
ボールの総数をMとしよう。
ボールをすべて取り出し、並べ替えてまた筒に入れる。
その際、各筒にあるボールの数は最初と同じで、かつ筒と同色のボールは入らないようにしたい。
同じ筒にあるボール群について、色の並びが異なる場合は異なる組み合わせとみなす場合、組み合わせは何通りあるか。
解法
筒が横1列に連結していると考え、ボールをM個並べることを考える。
i番目の筒から順に、その中にあるA[i]個のボールをi番より手前の空きスポットに入れるか、後ろのどこかに入れるかを考えよう。
f(i,n) := i番目までの筒を考えたとき、i番目までのボールのうちn個がすでに入る場所が決まっている場合の並び
を考える。なお、同色のボールの並びも区別するものとする。
この時、f(i,n)から(i+1)番目の筒の状態遷移を考えよう。
S=sum(A[1..n])とする。
(i+1)番目の筒にあるA[i+1]個のボールは、手前に残っている(S-n)個の空きスペースのどこかか、奥に残っているどこかに入る。
また、i番目までの筒のうち入る場所が未確定の(S-n)個のうちいくつかは、(i+1)番目の筒のどこかに入る。
A[i+1]個のボールのうちj個が手前に入り、(S-n)個のうちk個が(i+1)番目の筒に入るとすると、
となる。
最終的にf(N,0)に対し、同色のボールの並びの区別をしないよう、A[1]!*A[2]!....で割ったものが解。
int N,M; int A[2020]; int mo=1000000007; ll dp[2020][2020]; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll comb[2020][2020]; ll perm[2020][2020]; ll L[2020],F[2020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; FOR(i,2010) FOR(j,i+1) { perm[i][j]=fact[i]*factr[i-j]%mo; comb[i][j]=perm[i][j]*factr[j]%mo; } dp[0][0]=1; int sum=0,f; FOR(i,N) { cin>>A[i]; FOR(x,sum+1) if(dp[x][sum-x]) { dp[x][sum-x]%=mo; FOR(l,min(A[i],sum-x)+1) L[l]=perm[A[i]][l]*comb[sum-x][l]%mo; FOR(l,min(A[i],sum-x)+1) { FOR(f,min(A[i],sum-x)+1) { if(sum-x+A[i]-(f+l)<=M-(sum+A[i])) (dp[x+l+f][sum-x+A[i]-(f+l)]+=dp[x][sum-x]*L[l]%mo*L[f])%=mo; } } } sum+=A[i]; } ll ret=dp[M][0]; FOR(i,N) ret=ret*factr[A[i]]%mo; cout<<ret<<endl; }
まとめ
こっちは自力で解けたけど、時間内には終わらなかった。