Codeforcesに出そう。
http://community.topcoder.com/stat?c=problem_statement&pm=13764
問題
N個の箱が一列に並んでおり、そこに任意の順でN色のボールのどれかを1個ずつ入れていく(各色のボールは十分にある)。
その際、隣同士の箱に同じ色のボールが入ってないようにしたい。
そのような入れ方の組み合わせを考える際、以下の間違った入れ方で考えていくとする。
- ある箱にボールを入れる際、既に隣に1個ボールが入っているなら、それと異なる色を入れるのでその箱に入るボールの色は(N-1)通り。
- ある箱にボールを入れる際、既に両隣に2個ボールが入っているなら、それと異なる色を入れるのでその箱に入るボールの色は(N-2)通り。
- （なお、問題文中にあるとおりこの考え方は誤っている。両隣のボールの色が同じ場合を考慮していない）
上記誤った考え方でボールの色の組み合わせを考えるとする。
ボールの入れ方の順番をN!全通り試す場合、N!通りにおけるボールの色の組み合わせの和を求めよ。
解法
x個の連続した空き箱があり、かつそのx個の片隣、または両隣にボールが配置済みの場合、それらの空き箱の埋め方の組み合わせ数H(x), F(x)とする。
x=1～N-1まで順にDPでH(x), F(x)を求めていく。
例えばH(x)を求める場合、1～x番が空き箱で(x+1)番にボールが入っていると考える。
次にi番目にボールを入れる場合、残った箱の状態は(i-1)個の片隣にボールの入った箱と、(x-i)個の両隣にボールが入った箱の組み合わせが出る。
この両連続箱群のボールの埋め方はそれぞれH(i-1)、F(x-i)通りである。
また、残り(x-1)個の空き箱のうち(i-1)回は1～(i-1)番側の箱、(x-i)回は(i+1)～(x-i)番側の箱にボールを入れる。
よってといったようにDP出来る。
F(x)も同じ考え方でDP出来る。
最後に元の問題であるN個の空き箱の両隣にボールがない場合の組み合わせだが、ボールを1個置けば片隣にボールが埋まっている連続箱群2つの組にできるので、sum(F(i-1)*F(N-i))で求められる。
ll mo=1000000007; ll hc[4040]; ll fc[4040]; const int CN=4001; ll C[CN][CN]; class SumOverPermutations { public: int findSum(int n) { ZERO(hc); ZERO(fc); int i,j; FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo; hc[0]=fc[0]=1; hc[1]=n-1; fc[1]=n-2; for(i=2;i<n;i++) { FOR(j,i) { // half close if(j==0) hc[i] += (n-1)*hc[i-1]%mo; else hc[i] += n*fc[j]%mo*hc[i-1-j]%mo*C[i-1][j]%mo; //full close if(j==0||j==i-1) fc[i] += (n-1)*fc[i-1]%mo; else fc[i] += n*fc[j]%mo*fc[i-1-j]%mo*C[i-1][j]%mo; } hc[i]%=mo; fc[i]%=mo; } ll ret=0; FOR(i,n) { if(i==0 || i==n-1) ret += n*hc[n-1]%mo; else ret += n*hc[i]%mo*hc[n-1-i]%mo*C[n-1][i]%mo; } return ret%mo; } }
まとめ
本番はCombinationの分を最初考慮し忘れたが、すぐに思い出せて良かった。
450pt相当の問題かな？
