結果

問題 No.315 世界のなんとか3.5
ユーザー lam6er
提出日時 2025-03-31 17:35:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,303 bytes
コンパイル時間 4,381 ms
コンパイル使用メモリ 211,968 KB
実行使用メモリ 14,768 KB
最終ジャッジ日時 2025-03-31 17:36:22
合計ジャッジ時間 11,642 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

string decrement(string s) {
    int n = s.size();
    int i = n - 1;
    while (i >= 0 && s[i] == '0') {
        s[i] = '9';
        i--;
    }
    if (i == -1) return "0";
    s[i]--;
    if (s[i] == '0' && i == 0) {
        s.erase(s.begin());
        if (s.empty()) return "0";
    } else if (s[i] < '0') {
        s[i] += 10;
    }
    return s;
}

struct DPResult {
    int aho;
    int aho_p;
};

DPResult compute(const string &s, int P) {
    int n = s.size();
    vector<int> digits(n);
    for (int i = 0; i < n; ++i)
        digits[i] = s[i] - '0';
    
    // Compute aho
    vector<vector<vector<int>>> dp_prev_aho(2, vector<vector<int>>(3, vector<int>(2, 0)));
    dp_prev_aho[1][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        int d = digits[i];
        vector<vector<vector<int>>> dp_next_aho(2, vector<vector<int>>(3, vector<int>(2, 0)));
        for (int tight = 0; tight < 2; ++tight) {
            for (int sm = 0; sm < 3; ++sm) {
                for (int ht = 0; ht < 2; ++ht) {
                    if (dp_prev_aho[tight][sm][ht] == 0) continue;
                    int max_digit = (tight) ? d : 9;
                    for (int next_d = 0; next_d <= max_digit; ++next_d) {
                        int new_tight = (tight && (next_d == max_digit)) ? 1 : 0;
                        int new_sm = (sm + next_d) % 3;
                        int new_ht = ht || (next_d == 3);
                        dp_next_aho[new_tight][new_sm][new_ht] = 
                            (dp_next_aho[new_tight][new_sm][new_ht] + dp_prev_aho[tight][sm][ht]) % MOD;
                    }
                }
            }
        }
        dp_prev_aho = move(dp_next_aho);
    }
    int total_aho = 0;
    for (int tight = 0; tight < 2; ++tight)
        for (int sm = 0; sm < 3; ++sm)
            for (int ht = 0; ht < 2; ++ht)
                if (sm == 0 || ht)
                    total_aho = (total_aho + dp_prev_aho[tight][sm][ht]) % MOD;
    
    // Compute aho_p
    vector<vector<vector<vector<int>>>> dp_prev_ahop(2, vector<vector<vector<int>>>(3, vector<vector<int>>(2, vector<int>(P, 0))));
    dp_prev_ahop[1][0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        int d = digits[i];
        vector<vector<vector<vector<int>>>> dp_next_ahop(2, vector<vector<vector<int>>>(3, vector<vector<int>>(2, vector<int>(P, 0))));
        for (int tight = 0; tight < 2; ++tight) {
            for (int sm = 0; sm < 3; ++sm) {
                for (int ht = 0; ht < 2; ++ht) {
                    for (int rp = 0; rp < P; ++rp) {
                        if (dp_prev_ahop[tight][sm][ht][rp] == 0) continue;
                        int max_digit = (tight) ? d : 9;
                        for (int next_d = 0; next_d <= max_digit; ++next_d) {
                            int new_tight = (tight && (next_d == max_digit)) ? 1 : 0;
                            int new_sm = (sm + next_d) % 3;
                            int new_ht = ht || (next_d == 3);
                            int new_rp = (rp * 10 + next_d) % P;
                            dp_next_ahop[new_tight][new_sm][new_ht][new_rp] = 
                                (dp_next_ahop[new_tight][new_sm][new_ht][new_rp] + dp_prev_ahop[tight][sm][ht][rp]) % MOD;
                        }
                    }
                }
            }
        }
        dp_prev_ahop = move(dp_next_ahop);
    }
    int total_ahop = 0;
    for (int tight = 0; tight < 2; ++tight)
        for (int sm = 0; sm < 3; ++sm)
            for (int ht = 0; ht < 2; ++ht)
                for (int rp = 0; rp < P; ++rp)
                    if ((sm == 0 || ht) && rp == 0)
                        total_ahop = (total_ahop + dp_prev_ahop[tight][sm][ht][rp]) % MOD;
    
    return {total_aho, total_ahop};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string A, B;
    int P;
    cin >> A >> B >> P;
    
    string A_minus_1 = decrement(A);
    
    DPResult resB = compute(B, P);
    DPResult resA = compute(A_minus_1, P);
    
    int total_aho = (resB.aho - resA.aho + MOD) % MOD;
    int total_ahop = (resB.aho_p - resA.aho_p + MOD) % MOD;
    int ans = (total_aho - total_ahop + MOD) % MOD;
    
    cout << ans << "\n";
    
    return 0;
}
0