AtCoder ARC #075 : F - Mirrored

方針はすぐ立ったのにバグらせすぎた。
http://arc075.contest.atcoder.jp/tasks/arc075_d

問題

整数Nに対し、rev(N)とはNをleading zero抜きで10進数表記したものの桁の並びを反転させたものとする。
整数Dに対し、rev(N)=N+DとなるNの数を求めよ。

解法

Nの桁数を総当たりしつつ、対応する値を求めよう。

たとえばNの10進表記をabcdeとする。
rev(N)=edcbaなので、rev(N)-N=D=9999(e-a)+99(d-b)となる。

右辺は9の倍数なので、D/9=1111(e-a)+110(d-b)となる。
e-a=X、d-b=Yとし、D/9=1111X+110Yとおいてみる。
-9≦X≦9、-9≦Y≦9の範囲でこれを満たすX,Yを求めたいが、これは容易に求めることができる。
110Yの1の位は0にしかならないので、D/9の1の位とXの1の位は一致する。よってXは(正負で)高々2通り。Xが決まるとYの候補も決まる。
同様に、桁数が多い場合も端から順に各要素は2択で選んでいくことができる。

e-aの値が決まれば、aとeの組み合わせの数が決まり、同様にb,dの組み合わせも決まる。
これらは互いに独立なので掛け合わせていけなよい。
先頭のaだけは0を取れない点に注意すること。
また、奇数桁の場合真ん中の数字は何でもよい。

ll D;

ll hoge(ll A,ll t,int first) {
	if(t==0) return A==0;
	int v=(A%10+10)%10;
	ll ret=0;
	ret+=(10-v-first)*hoge((A-t*v)/10,t/100,0);
	ret+=(v-first)*hoge((A+(10-v)*t)/10,t/100,0);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D;
	if(D%9) return _P("0\n");
	D/=9;
	ll ret=0;
	ll p10=10;
	for(i=2;i<=18;i++) {
		p10*=10;
		
		ll tot=(i%2)?10:1;
		ret += tot*hoge(D,p10/10/9,1);
	}
	cout<<ret<<endl;
	
}

まとめ

正負両方の値を列挙する部分でバグらせまくった。