square869120Contest #1 : F - square1001の好きな回文数

バグとりにだいぶ手間取った。
http://s8pc-1.contest.atcoder.jp/tasks/s8pc_1_f

問題

最大80桁の正整数A,Bが与えられる。なお、どちらも桁数は偶数である。
A～Bの整数のうち、以下の条件を満たすものの数を求めよ。

• Cの倍数である
• 各桁の数字の総和がDである。
• 10進数表記・leading zero無しで回文である

解法

x以下で問題の条件を満たす整数の数をf(x)としたとき、f(B)-f(A-1)が解である。
よってあとはf(x)を求めよう。
Aは偶数桁だが、Aが10の累乗の場合A-1が奇数桁になってしまう。ただし1の位が0の正整数はそもそも回文ではないのでf(A-1)=f(A)となるため、その場合のみf(B)-f(A)を求めればよい。

まず前処理として、以下の値を求めよう。
g(d,m,s) := leading zeroも含め、d桁の整数で桁の総和がmであり、Cで割った余りがsとなる整数の数。
これはd-2桁の整数の両端に0～9を追加するDPで求められる。

上記gを用いてfを求めよう。
xをp桁の整数とし、v[i]をxの上からi桁目の数字を表すとする。
f(x)のうち、先頭i桁がxと一致する、条件を満たす数を順々に求めよう。
先頭i桁がxと一致するなら、上から(i+1)桁目の数字は0～(v[i]-1)でなければならない。
またそのような整数はf(p-(i+1)*2,m,s)個 (m,sはすでに決まった(i+1)*2桁を除いた桁数で、条件を満たすために取るべき値)あるので、それらを順次足していく。

string A,B,S;
int C,D;
int p10[101];
int all[101][55][1000];

int hoge(string v) {
	int ret=0;
	int L=v.size();
	
	int did=0;
	int mo=0;
	int d,i;
	
	for(int same=0;same<L/2;same++) {
		FOR(d,v[same]-'0') {
			int nmo=(mo+d*(p10[same]+p10[L-1-same]))%C;
			int ndid=did+2*d;
			FOR(i,C) if(ndid<=D && (i*p10[same+1]+nmo)%C==0) (ret+=all[L-(same+1)*2][i][D-ndid])%=10000;
		}
		mo+=(v[same]-'0')*(p10[same]+p10[L-1-same])%C;
		did+=2*(v[same]-'0');
	}
	
	string s=v.substr(0,L/2),s2=s;
	reverse(ALL(s2));
	s+=s2;
	if(s<=v && did==D && mo%C==0) ret++;
	
	return ret%10000;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D;
	if(A.back()!='0') A.back()--;
	
	p10[i]=1%C;
	for(i=1;i<=100;i++) p10[i]=p10[i-1]*10%C;
	
	all[0][0][0]=1;
	int d;
	for(i=2;i<=90;i+=2) {
		for(d=0;d<=9;d++) {
			int left=d*(1+p10[i-1])%C;
			FOR(x,C) for(y=0;y<=9*i;y++) {
				int nm=x*10+left;
				(all[i][nm%C][y+2*d]+=all[i-2][x][y])%=10000;
			}
		}
	}
	cout<<(20000+hoge(B)-hoge(A))%10000<<endl;
}

まとめ

本番「偶数」を見逃してしまい、偶奇どちらでも通るよう面倒なコードを書いてしまった。