kmjp's blog

競技プログラミング参加記です

Codeforces #341 Div2. E. Wet Shark and Blocks

すっかり忘れてた上にしょうもないミスで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したり、その後余りの計算で変数名ミスったりグダグダ。