すっかり忘れてた上にしょうもないミスでWAした。
http://codeforces.com/contest/621/problem/E
問題
1~9のうち重複ありでN個の整数からなる集合がある。
B個の集合から1個ずつ整数を選び、連結してB桁の10進数を作るとき、Xで割った剰余がKとなるのは何通りか。
(なお、集合に同じ整数が複数ある場合、それぞれ別の整数を選んだとして数える)
解法
F(d,m)を問題文の条件でd個の整数を選んだ時、Xで割った剰余がmとなる組み合わせとする。
ある整数pの末尾に1桁整数qを追加したときのXの剰余はp mod Xから((p mod X)*10+ q) mod Xに変化する。
この事から、F(d,m)を行列を用いた漸化式で表現できるので、行列累乗でF(B,K)を求めればよい。
計算量はO(X^3*logB)。
…のだが、自分はなぜか本番行列累乗を思いつかなかった。
平方分割でTLEしたので、立方分割でゴリ押した。
F(d,m)からF(d+1,n)は上記漸化式と同じ手順でDPで容易に求められる。
このDPを1000回分行うと、漸化式を1000回進めたとき、F(d,m)とF(d+1000,n)の関係が求められる。
同様に、F(d,m)からF(d+1000,n)を求めることを1000回DP繰り返すと、F(d,m)とF(d+1000000,n)の関係が求められる。
これで漸化式を10^6回・10^3回・1回進めた時の値が分かるので、これらを使い計B回漸化式を進めればよい。
計算量はO(B^(1/3)*X^2)。
int N,B,K,X; ll fact[101010]; ll fact2[101010]; ll fact3[101010]; int OC[11]; ll dp[1050][100]; ll dp2[1050][100]; ll dp3[1050][100]; ll mo=1000000007; void solve() { int i,j,k,l,r,x,y,z; string s; cin>>N>>B>>K>>X; FOR(i,N) cin>>x, OC[x]++; fact[0]=fact2[0]=fact3[0]=1; FOR(i,1020) fact[i+1]=fact[i]*10%X; FOR(i,1020) fact2[i+1]=fact2[i]*fact[1000]%X; FOR(i,1020) fact3[i+1]=fact3[i]*fact2[1000]%X; dp[0][0]=dp2[0][0]=dp3[0][0]=1; FOR(i,1000) FOR(y,X) FOR(x,10) (dp[i+1][(y*10+x)%X] += dp[i][y]*OC[x])%=mo; FOR(i,1000) FOR(x,X) FOR(y,X) (dp2[i+1][(fact2[1]*y+x)%X] += dp2[i][y]*dp[1000][x])%=mo; FOR(i,1001) FOR(x,X) FOR(y,X) (dp3[i+1][(fact3[1]*y+x)%X] += dp3[i][y]*dp2[1000][x])%=mo; ll ret=0; FOR(x,X) FOR(y,X) FOR(z,X) if((z*fact3[B/1000000]*fact2[B/1000%1000]+y*fact3[B/1000000]+x)%X==K) (ret+=dp[B%1000][z]*dp3[B/1000000][x]%mo*dp2[B/1000%1000][y])%=mo; cout<<ret<<endl; }
まとめ
平方分割でTLEしたり、その後余りの計算で変数名ミスったりグダグダ。