ややこしいDP。
http://codeforces.com/contest/1439/problem/D
問題
整数N,Mが与えられる。
1~Nの番号を持つN台のPCが左右1列に並んでいる。
ここで、M人の生徒がこれらを利用することになるが、各生徒iには2つのパラメータA[i]とB[i]を持つ。
生徒は1番の生徒から順にきて、以下のようにPCを利用する。
- B[i]は左右のいずれかを示す。各生徒は、B[i]の側から反対側に向けて移動し、A[i]番目のPCの前で止まる。
- ただし、A[i]番目のPCの前に、それ以前に来た生徒が止まっている場合、そこを超えてその先の最初の未使用PCの前で止まる。
- もし未使用PCがなく反対側の端まで移動してしまった場合、そのパラメータは無効とする。
有効なパラメータ全通りについて、各生徒iが停止したPC番号をC[i]としたとき、|A[i]-C[i]|の総和を求めよ。
解法
まずN=Mの時を考える。
dp1(i) := N=M=iの時の、有効なパラメータの組み合わせ
dp2(i) := N=M=iの時の、有効なパラメータの組み合わせにおける|A[j]-C[j]|の総和
dp1(i)は、最後の人がj番目の席に座るケースを考えると(i+1)*dp1(j-1)*dp1(i-j)*comb(i-1,j-1)通り考えられる。
jを総当たりすればO(N^2)でdp1(N)を求められる。
dp2(i)も最後の人がj番目に座るケースを考えると計算できる。
次にN>Mの時を考える。
dp3(i,j) := N=i、M=jの時の有効なパラメータの組み合わせ
dp4(i,j) := N=i、M=jの時の有効なパラメータの組み合わせにおける|A[k]-C[k]|の総和
dp3の計算では、空き席を挟みながら、連続して占有された領域を配置することを考えると、dp1を用いて計算していくことができる。
dp4の計算も、dp3とdp2の計算方法を組み合わせて計算できる。
ll mo; struct modint { ll v; modint(const ll a=0) { v=a; if(mo&&(v>=mo||v<0)) v=(v%mo+mo)%mo;} static modint pow(const modint& a,ll n=mo-2) { ll b=a.v,r=1; while(n) r=r*((n%2)?b:1)%mo,b=b*b%mo,n>>=1; return modint(r); } modint& operator+=(const modint& a) { v+=a.v; if(v>=mo) v-=mo; return *this;} modint& operator-=(const modint& a) { v+=mo-a.v; if(v>=mo) v-=mo; return *this;} modint& operator*=(const modint& a) { v=v*a.v%mo; return *this;} modint& operator/=(const modint& a) { assert(a.v!=0); *this*=pow(a); return *this;} modint operator+(const modint& a) const { modint res(*this); return res+=a;} modint operator-(const modint& a) const { modint res(*this); return res-=a;} modint operator*(const modint& a) const { modint res(*this); return res*=a;} modint operator/(const modint& a) const { modint res(*this); return res/=a;} friend ostream& operator<<(ostream& os, const modint& a){ os<<a.v; return os;} }; int N,M; modint dp1[505]; modint dp2[505]; modint dp3[505][505]; modint dp4[505][505]; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { 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; } if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>mo; dp1[0]=1; for(i=1;i<=N;i++) { for(j=1;j<=i;j++) { dp1[i]+=modint(i+1)*dp1[j-1]*dp1[i-j]*comb(i-1,j-1); dp2[i]+=modint(i+1)*(dp2[i-j]*dp1[j-1]+dp1[i-j]*dp2[j-1])*comb(i-1,j-1); dp2[i]+=dp1[j-1]*dp1[i-j]*comb(i-1,j-1)*(comb(j-1+1,2)+comb(i-j+1,2)); } } dp3[0][0]=1; for(i=1;i<=N;i++) { FOR(j,i) { dp3[i][j]=dp3[i-1][j]; dp4[i][j]=dp4[i-1][j]; for(l=1;l<=j;l++) { dp3[i][j]+=dp1[l]*dp3[i-l-1][j-l]*comb(j,l); dp4[i][j]+=(dp1[l]*dp4[i-l-1][j-l]+dp2[l]*dp3[i-l-1][j-l])*comb(j,l); } } dp3[i][i]=dp1[i]; dp4[i][i]=dp2[i]; } cout<<dp4[N][M]<<endl; }
まとめ
こういうDP、さっと組める気がしないな。