#1061829 (C++17) No.315 世界のなんとか3.5

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX