10^9と10^9+7と回文 [yukicoder No.528] - はまやんはまやんはまやん

解説動画

解法

http://yukicoder.me/submissions/179274
動画解説を見て欲しい。
以下の手順で解く。
1. [1,n-1]桁の回分数を数え上げる
2. n桁の回分数を数え上げる
2-1. n桁の回分数の上半分の桁が最大となる一個前まで数える
2-2. n桁の回分数の上半分の桁が最大となる場合がN以下であるか判定する
これを丁寧にやると答えが求まる。

string N;
int n;
//---------------------------------------------------------------------------------------------------
int to_integer(string s, int mod) {
    int res = 0;
    rep(i, 0, s.length()) {
        int c = s[i] - '0';
        res = (1LL * res * 10 + c) % mod;
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
int count(int mod) {
    int len = (n + 1) / 2;

    string pre = N.substr(0, len);
    int ma = to_integer(pre, mod);

    string line = "1";
    rep(i, 0, len - 1) line += "0";
    int mi = to_integer(line, mod);

    return (ma - mi + mod) % mod;
}
//---------------------------------------------------------------------------------------------------
int solve(int mod) {
    n = N.length();
    int ans = 0;

    // 1
    rep(len, 1, n) {
        int d = mul(mod, 9, modpow(mod, 10, (len - 1) / 2));
        ans = add(mod, ans, d);
    }

    // 2-1
    ans = add(mod, ans, count(mod));

    // 2-2
    if (n % 2 == 0) {
        bool ok = true;
        rep(i, 0, n / 2) {
            if (N[n / 2 - 1 - i] > N[i + n / 2]) ok = false;
            if (N[n / 2 - 1 - i] < N[i + n / 2]) break;
        }
        if (ok) ans = add(mod, ans, 1);
    } else {
        bool ok = true;
        rep(i, 0, n / 2) {
            if (N[n / 2 - 1 - i] > N[i + n / 2 + 1]) ok = false;
            if (N[n / 2 - 1 - i] < N[i + n / 2 + 1]) break;
        }
        if (ok) ans = add(mod, ans, 1);
    }

    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    cout << solve(1000000000) << endl;
    cout << solve(1000000007) << endl;
}

【追記】n桁の回分数の上半分の桁が最大となる一個前まで数えるの具体的な実装手順

「10000…～最大の1つ前」を数える手順
文字列の数をmodで数に直す関数
先頭の数から10倍して足す、10倍して足すとしていくと文字列の数を数にできる。
このときにmodを取りながらやると適切に数にできる。

int to_integer(string s, int mod) {
    int res = 0;
    rep(i, 0, s.length()) {
        int c = s[i] - '0';
        res = (1LL * res * 10 + c) % mod;
    }
    return res;
}

最大の数を取得する
上半分の文字列を取ってきて数に直す

int len = (n + 1) / 2;
string pre = N.substr(0, len);
int ma = to_integer(pre, mod);

最小の数を取得する
最初が1で残りが(len-1)個の0である数の文字列を作って数に直す

string line = "1";
rep(i, 0, len - 1) line += "0";
int mi = to_integer(line, mod);

あとは、最大と最小の差を取れば、一個前まで数えることができる。
今回は計算量があまり問題にならないので、文字列の状態を挟んでおくと、比較的デバッグがし易いのでオススメ。