F. Mirrored [AtCoder Regular Contest 075]

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

解説（複雑で適当なので微妙な解説）

http://arc075.contest.atcoder.jp/submissions/1328295
メモ化再帰で解いていく。
あらかじめ、Dは頭に0を追加して24桁にしておく。

以下のような関数を定義する。
f(L, R, Lu, Ru) [L,R]桁目がまだ未確定で、繰り上がり分としてLuが必要で、R桁目未満からの繰り上がりがRuであるときに有効な組合せ

これを使うと、答えはf(0,23,0,0)+f(1,23,0,0)+...+f(x,23,0,0)である。
（xは初めて0以外が出てくる最も左の桁目）

関数の中身はR==23かどうかで分岐しているが、これは、R==23なら先頭は0ではダメ、R!=23なら先頭は0でも良いというLeading-Zero対策の分岐である。

その中で基本的には、L桁目とR桁目に置く数字を全列挙していく。
L桁目に置く数字は反転してR桁目に来るので、条件が合うようなものだけ、利用していく。

string D;
//---------------------------------------------------------------------------------------------------
int memo[24][24][2][2];
int f(int L, int R, int Lu, int Ru) {
    int &res = memo[L][R][Lu][Ru];
 
    if (0 <= res) return res;
 
    res = 0;
 
    if (R == 23) {
        if (L == R) res = 0;
        else if(L + 1 == R) {
            rep(a, 1, 10) rep(b, 0, 10) {
                int t = b + D[R] - '0' + Ru;
                int tt = t / 10;
                if (t % 10 != a) continue;
                int s = a + D[L] - '0' + tt;
                if (s % 10 != b) continue;
                if (s / 10 != Lu) continue;
                res++;
                //printf("(%d %d)\n", a, b);
            }
        } else {
            rep(a, 1, 10) rep(b, 0, 10) {
                if ((b + D[R] - '0' + Ru) % 10 != a) continue;
                int Ruu = (b + D[R] - '0' + Ru) / 10;
 
                if ((a + D[L] - '0') / 10 == Lu && (a + D[L] - '0') % 10 == b) res += f(L + 1, R - 1, 0, Ruu);
                if ((a + D[L] - '0' + 1) / 10 == Lu && (a + D[L] - '0' + 1) % 10 == b) res += f(L + 1, R - 1, 1, Ruu);
            }
        }
    } else {
        if (L == R) {
            rep(a, 0, 10) {
                if ((a + D[L] - '0' + Ru) / 10 != Lu) continue;
                if ((a + D[L] - '0' + Ru) % 10 != a) continue;
                res++;
                //printf("[%d]\n", a);
            }
        } else if (L + 1 == R) {
            rep(a, 0, 10) rep(b, 0, 10) {
                int t = b + D[R] - '0' + Ru;
                int tt = t / 10;
                if (t % 10 != a) continue;
                int s = a + D[L] - '0' + tt;
                if (s % 10 != b) continue;
                if (s / 10 != Lu) continue;
                res++;
                //printf("<%d %d>\n", a, b);
            }
        } else {
            rep(a, 0, 10) rep(b, 0, 10) {
                if ((b + D[R] - '0' + Ru) % 10 != a) continue;
                int Ruu = (b + D[R] - '0' + Ru) / 10;
 
                if ((a + D[L] - '0') / 10 == Lu && (a + D[L] - '0') % 10 == b) res += f(L + 1, R - 1, 0, Ruu);
                if ((a + D[L] - '0' + 1) / 10 == Lu && (a + D[L] - '0' + 1) % 10 == b) res += f(L + 1, R - 1, 1, Ruu);
            }
        }
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> D;
    while (D.size() < 24) D = "0" + D;
    rep(L, 0, 24) rep(R, 0, 24) rep(Lu, 0, 2) rep(Ru, 0, 2) memo[L][R][Lu][Ru] = -1;
    //cout << D << endl;
    int L = 0;
    while (D[L] == '0') L++;
    int ans = 0;
    rep(x, 0, L + 1) {
        //printf("{{ %d }}\n", x);
        ans += f(x, 23, 0, 0);
    }
    cout << ans << endl;
    
}