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

• 問題: No.315 世界のなんとか3.5
• ユーザー: koyumeishi
• 提出日時: 2015-09-20 01:00:18
• 言語: C++11 (gcc 13.3.0)
• 結果: WA
• 実行時間: -
• コード長: 2,370 bytes
• コンパイル時間: 661 ms
• コンパイル使用メモリ: 80,708 KB
• 実行使用メモリ: 6,948 KB
• 最終ジャッジ日時: 2024-07-19 08:15:46
• 合計ジャッジ時間: 4,750 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
other	AC * 6 WA * 30

ソースコード

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
//WA
//aが答えに含まれていた時を見落とした場合WAが出るか確認
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MOD 1000000007
int P;
long long func(string& s){
    //dp[mod_P][lower | has3 | mod3]
    
    vector<vector<long long>> dp (P, vector<long long>(16, 0));
    vector<vector<long long>> dp_(P, vector<long long>(16, 0));
    int keta;
    int tmp = P;
    int two = 0;
    int five = 0;
    while(tmp%2==0){
        tmp/=2;
        two++;
    }
    while(tmp%5==0){
        tmp/=5;
        five++;
    }
    keta = max(two, five);
    dp[0][0b0000] = 1;
    for(int i=0; i<s.size(); i++){
        for(int j=0; j<( (s.size()-i< keta) ?P:1); j++){
            fill(dp_[j].begin(), dp_[j].end(), 0);
        }
        for(int lower=0; lower<2; lower++)
        for(int has3=0; has3<2; has3++)
        for(int mod3=0; mod3<3; mod3++)
        {
            int state = (lower<<3) | (has3<<2) | mod3;
            for(int d=0; d<10; d++){
                if(lower==0 && d>s[i]-'0') continue;
                int next_state = (lower || d<s[i]-'0')<<3;
                next_state |= (has3 || d==3)<<2;
                next_state |= (mod3*10+d)%3;
                if(s.size()-i > keta){
                    long long& dp_now = dp[0][state];
                    long long& dp_next = dp_[0][next_state];
                    dp_next += dp_now;
                    if(dp_next>=MOD) dp_next -= MOD;
                }else for(int mod_P=0; mod_P<P; mod_P++){
                    long long& dp_now  = dp[mod_P][state];
                    long long& dp_next = dp_[(mod_P*10+d)%P][next_state];
                    dp_next += dp_now;
                    if(dp_next>=MOD) dp_next -= MOD;
                }
            }
        }
        swap(dp, dp_);
    }
    long long ret = 0;
    for(int mod_P=1; mod_P<P; mod_P++){
        if(mod_P % P == 0) continue;
        for(int lower=0; lower<2; lower++)
        for(int has3=0; has3<2; has3++)
        for(int mod3=0; mod3<3; mod3++)
        {
            int state = (lower<<3) | (has3<<2) | mod3;
            if( has3==0 && mod3!=0 ) continue;
            ret += dp[mod_P][state];
            if(ret>=MOD) ret -= MOD;
        }
    }
    return ret;
}
int main(){
    string a,b;
    cin >> a >> b;
    cin >> P;
    
    long long ans = 0;
    ans += func(b);
    ans -= func(a);
    ans = (ans+MOD)%MOD;
/*
    int mod3 = 0;
    int has3 = 0;
    int mod_P = 0;
    for(int i=0; i<a.size(); i++){
        if(a[i] == '3') has3 = 1;
        mod3 = (mod3*10 + a[i]-'0') % 3;
        mod_P = (mod_P*10 + a[i]-'0') % P;
    }
    if( (mod3==0 || has3==1) && mod_P!=0 ) ans += 1;
    ans = (ans+MOD)%MOD;
*/
    cout << ans << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX