ARC075 F Mirrored

問題文

https://arc075.contest.atcoder.jp/tasks/arc075_d

 

ケタ数を固定することにし,kケタの整数で,rev(N)=N+DとなるNを数えることにする.

10^iのケタの数字をa[i]とすると,N=Σa[i]*10^iでrev(N)=Σa[k-i-1]*10^iとなるから,

rev(N)-N=Σ(a[k-i-1]-a[i])*10^i=Dとなるようaを決める方法が何通りかを数えることになる.

ここでa[k-1]-a[0]≡D(mod 10)であることがわかる.例えばD=63ならa[k-1]-a[0]=3 or -7の二択である.

このうちどちらかに固定してやると,同様にしてa[k-2]-a[1]の値も二択になる.こうしていくと,結局2^(k/2)通り試してやればこのようなNを全て数えることが出来る.

あとは固定するkをどこまで試せばいいかだが,これは1から18まで試せばよい.

※Dのケタ数の2倍まで試せば良いことをちゃんと示せてない

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll ten[19];
ll dfs(int k, int L, ll x) {
    if (k == L / 2) {
        if (x) return 0;
        if (L % 2) return 10;
        return 1;
    }
    ll d[2];
    if (x >= 0) {
        d[0] = x % 10;
        d[1] = d[0] - 10;
    }
    else {
        d[0] = -((-x) % 10);
        d[1] = d[0] + 10;
    }
    ll ret = 0;
    for (int i = 0; i < 2; i++) {
        if (i == 1 && abs(x) % 10 == 0) break;
        ll y = x - d[i] * (1 - ten[L - 1 - 2 * k]);
        if (y % 10) continue;
        y /= 10;
        ll add = dfs(k + 1, L, y);
        if (k == 0) add *= 9 - abs(d[i]);
        else add *= 10 - abs(d[i]);
        ret += add;
    }
    return ret;
}
int main() {
    int D;
    cin >> D;
    ten[0] = 1;
    for (int i = 1; i <= 18; i++) ten[i] = ten[i - 1] * 10;
    ll ans = 0;
    for (int L = 1; L <= 18; L++) {
        ans += dfs(0, L, D);
    }
    cout << ans << endl;
}