Codeforces ECR #008 : D. Magic Numbers

本番４問しか解けなかったうえ、まさかのC,DミスでAB2完のみ。ratedでないコンテストで助かった。
http://codeforces.com/contest/628/problem/D

問題

正の整数がd-magicであるとは以下を満たす場合をいう。

• 上から奇数番目の桁の値はd以外である。
• 上から偶数番目の桁の値はdである。

２つの同じ桁数の整数A,Bが与えられる。[A,B]の区間にあるd-magicな値で、かつMで割り切れる値の数を求めよ。

解法

典型的な桁DP。

まず以下をDPで求めよう。leading zeroも許可する。
dp[a][b] := 後ろa桁がd-magicの条件を満たし、かつMで割った余りがbとなるものの数

f(n)を、0～nの間で問題文の条件を満たす値の数とすると、f(B)-f(A-1)が解。

あとはf(n)を上の桁から順にDPする。
幸い、求めたいのは[A,B]の区間だけであり、AとBは同じ桁数であることから、最上位桁が0になるケースは考える必要がなく、leading zeroを気にする必要がない。

int M,D;
string A,B;
ll mo=1000000007;
ll p10[2020];
ll memo[2020][2020];

string decdec(string A) {
	reverse(A.begin(),A.end());
	FORR(r,A) {
		if(r!='0') {
			r--;
			break;
		}
		r='9';
	}
	if(A.back()=='0') A.resize(A.size()-1);
	reverse(A.begin(),A.end());
	return A;
}

ll dodo(string S) {
	int L=S.size();
	int i,j,x;
	ll ret=0;
	int r=0;
	FOR(i,L) {
		if(i%2==0) {
			FOR(x,S[i]-'0') {
				if(i==0 && x==0) continue;
				if(x==D) continue;
				int r2=(r+x*p10[L-1-i])%M;
				ret += memo[L-1-i][(M-r2)%M];
			}
			if(S[i]-'0'==D) break;
			r+=(S[i]-'0')*p10[L-1-i];
			r%=M;
			
		}
		else {
			if(S[i]-'0'>D) {
				r+=D*p10[L-1-i];
				r%=M;
				ret+=memo[L-1-i][(M-r)%M];
				break;
			}
			else if(S[i]-'0'==D) {
				r+=D*p10[L-1-i];
				r%=M;
			}
			else {
				break;
			}
			
		}
		ret%=mo;
	}
	if(i==L&&r==0) ret++;
	return ret%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>D;
	cin>>A>>B;
	if(A.size()<=2) {
		x=atoi(A.c_str());
		y=atoi(B.c_str());
		r=0;
		if(A.size()==1) {
			for(i=x;i<=y;i++) if(i!=D && i%M==0) r++;
		}
		else {
			for(i=x;i<=y;i++) if(i%10==D && i/10!=D && i%M==0) r++;
		}
		cout<<r<<endl;
		return;
	}
	
	ll ret=0;
	if(!(A[0]=='1' && count(ALL(A),'0')==A.size()-1)) A=decdec(A);
	
	p10[0]=1%M;
	FOR(i,2010) p10[i+1]=p10[i]*10%M;
	
	memo[0][0]++;
	for(j=1;j<=2002;j++) {
		FOR(x,M) {
			FOR(i,10) {
				if((A.size()-j)%2==1 && i!=D) continue;
				if((A.size()-j)%2==0 && i==D) continue;
				int v=i*p10[j-1];
				(memo[j][(v+x)%M] += memo[j-1][x])%=mo;
			}
		}
	}
	
	
	cout<<(mo+ret+dodo(B)-dodo(A))%mo<<endl;
	
}

まとめ

非常に面倒な上、最終的にミスした…。