Codeforces #287 Div2 D. The Maths Lecture

Eよりこっちの方が迷った。
http://codeforces.com/contest/507/problem/D

問題

整数N,K,Mが与えられる。
10進数で(leading zeroを含まない)N桁の数xのうち、suffixが非0のKの倍数となるような物の数をMで割った余りを答えよ。

解法

d桁の(非0な)Kの倍数があると、その数値をsuffixとするN桁の数個(最上位桁は0をとれないため10^(N-d)ではない)のxが答えの対象となる。

よってDPで状態として[桁数d][Kの余り]に対応するd桁の数の組み合わせ数を求め、余りが0になる度にに答えを計上していけば良い。
ただし、suffixが0であることは認められないので、状態としてさらに0か非0かの判定フラグも持つ必要がある。

ll N,K,M;

ll momo[1012];
ll momo2[1012];
ll dp[2][1010][105];
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>M;
	
	momo[0]=momo2[0]=1;
	FOR(i,N+1) momo[i+1]=momo[i]*10%K;
	FOR(i,N+1) momo2[i+1]=momo2[i]*10%M;
	
	dp[0][0][0]=1;
	FOR(i,N) {
		FOR(k,2) FOR(j,10) {
			FOR(x,K) {
				y=(x+momo[i]*j)%K;
				if(y==0 && (k||j)) {
					if(i==N-1) ret+=dp[k][i][x];
					else ret+=9*momo2[N-i-2]*dp[k][i][x];
					ret %= M;
				}
				else {
					if(k || j) (dp[1][i+1][y]+=dp[k][i][x])%=M;
					else (dp[0][i+1][y]+=dp[k][i][x])%=M;
				}
			}
		}
	}
	
	cout<<ret<<endl;;
}

まとめ

桁DPは上の桁からやるイメージが強く、それに引っ張られてタイムロスした。
suffixが出てくる問題だから下の桁から処理するのは当然か…。