結果

問題 No.528 10^9と10^9+7と回文
ユーザー vjudge1
提出日時 2025-05-17 18:30:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,881 bytes
コンパイル時間 801 ms
コンパイル使用メモリ 69,076 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-17 18:30:19
合計ジャッジ時間 2,622 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MOD1 = 1e9 + 9;
const int MOD2 = 1e9 + 7;
int pow_mod(int a, int b, int mod) {
    int res = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            res = (long long)res * a % mod;
        }
        a = (long long)a * a % mod;
        b /= 2;
    }
    return res;
}
int str_mod(const string &s, int mod) {
    int res = 0;
    for (char c : s) {
        res = ((long long)res * 10 + (c - '0')) % mod;
    }
    return res;
}

int main() {
    string n_str;
    cin >> n_str;
    int m = n_str.size();
    int sum_less_mod1 = 0, sum_less_mod2 = 0;
    for (int k = 1; k < m; ++k) {
        int e = (k - 1) / 2;
        int term1 = (9LL * pow_mod(10, e, MOD1)) % MOD1;
        sum_less_mod1 = (sum_less_mod1 + term1) % MOD1;
        int term2 = (9LL * pow_mod(10, e, MOD2)) % MOD2;
        sum_less_mod2 = (sum_less_mod2 + term2) % MOD2;
    }
    
    int s = (m + 1) / 2;
    string pre_str = n_str.substr(0, s);
    string pal_str;
    if (m % 2 == 0) {
        pal_str = pre_str + string(pre_str.rbegin(), pre_str.rend());
    } else {
        pal_str = pre_str + string(pre_str.rbegin() + 1, pre_str.rend());
    }
    bool compare = pal_str > n_str;
    int pre_mod1 = str_mod(pre_str, MOD1);
    int pre_mod2 = str_mod(pre_str, MOD2);
    int start_mod1 = pow_mod(10, s - 1, MOD1);
    int start_mod2 = pow_mod(10, s - 1, MOD2);
    int delta_mod1 = (pre_mod1 - start_mod1 + MOD1) % MOD1;
    int delta_mod2 = (pre_mod2 - start_mod2 + MOD2) % MOD2;
    int count_m_mod1 = compare ? delta_mod1 : (delta_mod1 + 1) % MOD1;
    int count_m_mod2 = compare ? delta_mod2 : (delta_mod2 + 1) % MOD2;
    int total_mod1 = (sum_less_mod1 + count_m_mod1) % MOD1;
    int total_mod2 = (sum_less_mod2 + count_m_mod2) % MOD2;
    cout << total_mod1 << endl << total_mod2 << endl;
    return 0;
}
0