これ方針は合ってたので最後まで解ききれなかったの残念。
https://community.topcoder.com/stat?c=problem_statement&pm=15405
問題
整数Sと、2つのN要素の整数列A,Bが与えられる。A,Bの総和はS以上である。
SからA[0],B[0],A[1],B[1],....と順に値を引いていき、Sが0以下になったところで止める、ということを考える。
A,Bそれぞれ並び順を変えることを考えると、(N!)^2通りの並べ替え方がある。
この時、B側の値を引いた段階でS以下になる、という状態は何通りあるか。
解法
(並べ替え前の)値B[i]が、並べ替え後(0-originで)j番目に来た場合に条件を満たすのは何通りか、(i,j)を列挙することを考える。
その場合、Aから選ぶ先頭(j+1)個と、Bから選ぶ先頭(j)個の和が、S-B[i]以上S-1以下であればB[i]を(j+1)回目に引いた時点でSが0以下になる。
よってこの組み合わせを列挙しよう。
必要なのは和だけなので、並び順はあとで考えるとしてまずは以下をDPで求める。
f(n,k) := Aからn個選択して和がkとなる組み合わせ数
g(n,k) := Bからn個選択して和がkとなる組み合わせ数
ここで、
g'(n,k) := Bから「元のB[i]以外で」n個選択して和がkとなる組み合わせ数
とするものを考えよう。
するとが求まれば、Aの先頭(j+1)個およびBの先頭(j)個の組み合わせが列挙できるので、そこにを掛ければ並び順も含めた組み合わせが求められる。
総和の式は、g'(j,l)についてはlの累積和を取っておけば、kだけ総当たりすればよくなる。
あとはg'(n,k)だが、これはいわゆる戻すDPである。
g(n,k) = g'(n,k) + g'(n-1, k-B[i])なので、g'(n,k) = g(n,k)-g'(n-1,k-B[i])となる。
g'(0,l)はl=0なら1、それ以外0で明らかなので、nの小さい順にg'(n,k)を確定させていくことができる。
ll X[101][10101]; ll Y[101][10101]; ll Z[101][10101]; ll W[10101],SS[10101]; ll mo=1000000007; ll fact[201]; class PrettyLiar { public: int count(int S, vector <int> A, vector <int> B) { ZERO(X); ZERO(Y); ZERO(Z); int N=A.size(); int i,a,b,j,x,y; fact[0]=1; for(i=1;i<=200;i++) fact[i]=fact[i-1]*i%mo; X[0][0]=Y[0][0]=Z[0][0]=1; FOR(i,N) { for(a=i;a>=0;a--) FOR(b,a*100+1) { X[a+1][b+A[i]]+=X[a][b]; if(X[a+1][b+A[i]]>=mo) X[a+1][b+A[i]]-=mo; Y[a+1][b+B[i]]+=Y[a][b]; if(Y[a+1][b+B[i]]>=mo) Y[a+1][b+B[i]]-=mo; } } ll ret=0; FOR(i,N) { int b=B[i]; for(x=1;x<=N;x++) { ll pat=fact[x]%mo*fact[N-x]%mo*fact[x-1]%mo*fact[N-x]%mo; FOR(j,x*100+1) { Z[x][j]=Y[x][j]; if(j>=b) { Z[x][j]+=mo-Z[x-1][j-b]; if(Z[x][j]>=mo) Z[x][j]-=mo; } W[j]=Z[x-1][j]; if(j) W[j]+=W[j-1]; if(W[j]>=mo) W[j]-=mo; } FOR(j,x*100+1) if(X[x][j]) { int L=S-b-j,R=min(x*100,S-j-1); if(R<0 || R<L) continue; ll sum=W[R]; if(L>0) sum+=mo-W[L-1]; if(sum) ret+=X[x][j]*sum%mo*pat%mo; } ret%=mo; } } return ret; } }
まとめ
戻すDPを使うことまでは到達したのに、そのやり方を間違えてアウトだった。
もったいないけど勉強にはなったか。