結果

問題 No.315 世界のなんとか3.5
ユーザー mayoko_mayoko_
提出日時 2015-12-08 14:07:34
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 219 ms / 2,000 ms
コード長 5,298 bytes
コンパイル時間 926 ms
コンパイル使用メモリ 91,380 KB
実行使用メモリ 24,192 KB
最終ジャッジ日時 2024-09-14 20:08:56
合計ジャッジ時間 4,685 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 21 ms
23,424 KB
testcase_03 AC 8 ms
5,376 KB
testcase_04 AC 10 ms
5,376 KB
testcase_05 AC 6 ms
5,376 KB
testcase_06 AC 7 ms
5,376 KB
testcase_07 AC 6 ms
5,376 KB
testcase_08 AC 20 ms
23,296 KB
testcase_09 AC 19 ms
23,424 KB
testcase_10 AC 20 ms
23,296 KB
testcase_11 AC 19 ms
23,296 KB
testcase_12 AC 57 ms
23,424 KB
testcase_13 AC 57 ms
23,296 KB
testcase_14 AC 94 ms
23,552 KB
testcase_15 AC 94 ms
23,552 KB
testcase_16 AC 96 ms
23,552 KB
testcase_17 AC 95 ms
23,680 KB
testcase_18 AC 57 ms
23,424 KB
testcase_19 AC 57 ms
23,424 KB
testcase_20 AC 65 ms
23,424 KB
testcase_21 AC 66 ms
23,424 KB
testcase_22 AC 102 ms
23,552 KB
testcase_23 AC 104 ms
23,552 KB
testcase_24 AC 95 ms
23,552 KB
testcase_25 AC 103 ms
23,680 KB
testcase_26 AC 95 ms
23,680 KB
testcase_27 AC 94 ms
23,552 KB
testcase_28 AC 99 ms
23,552 KB
testcase_29 AC 153 ms
24,192 KB
testcase_30 AC 146 ms
24,064 KB
testcase_31 AC 144 ms
24,064 KB
testcase_32 AC 177 ms
24,064 KB
testcase_33 AC 103 ms
23,680 KB
testcase_34 AC 128 ms
24,192 KB
testcase_35 AC 219 ms
24,064 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

const ll MOD = 1e9+7;
const int MAXN = 200020;
ll dp[MAXN][2][2][3]; // n, big, exist3, mod3
ll memo1[10][2][2][3][800]; // n, big, exist3, mod3, modP
ll memo2[10][2][3][800]; // n, exist3, mod3, modP
ll memo[2][2][3]; // すでにbigと決定, exist3, mod3

int check(string A, int P) {
    int sum = 0, exist3 = 0, modP = 0;
    for (char c : A) {
        int num = c-'0';
        sum += num;
        exist3 |= (num==3);
        modP = (modP*10+num)%P;
    }
    if (modP) {
        if (sum%3 == 0 || exist3) return 1;
    }
    return 0;
}

ll calc(string s, int P) {
    if (s.size() <= 5) {
        int A = stoi(s);
        ll ans = 0;
        for (int i = 0; i <= A; i++) {
            if (check(to_string(i), P)) ans++;
        }
        return ans;
    }
    memset(memo1, 0, sizeof(memo1));
    memset(memo2, 0, sizeof(memo2));
    memset(memo, 0, sizeof(memo));
    memset(dp, 0, sizeof(dp));
    int n = s.size();
    string t = s.substr(n-5);
    // memo1 を求める
    memo1[0][0][0][0][0] = 1;
    for (int i = 0; i < 5; i++) for (int big = 0; big < 2; big++) {
        for (int e3 = 0; e3 < 2; e3++) for (int m3 = 0; m3 < 3; m3++) for (int mp = 0; mp < P; mp++) {
            if (big) {
                for (int j = 0; j < 10; j++) {
                    int nm3 = (m3+j)%3, nmp = (mp*10+j)%P;
                    int ne3 = e3;
                    ne3 |= (j==3);
                    memo1[i+1][big][ne3][nm3][nmp] += memo1[i][big][e3][m3][mp];
                    memo1[i+1][big][ne3][nm3][nmp] %= MOD;
                }
            } else {
                int num = t[i]-'0';
                for (int j = 0; j <= num; j++) {
                    int nm3 = (m3+j)%3, nmp = (mp*10+j)%P;
                    int ne3 = e3;
                    ne3 |= (j==3);
                    int nbig = (j<num);
                    memo1[i+1][nbig][ne3][nm3][nmp] += memo1[i][big][e3][m3][mp];
                    memo1[i+1][nbig][ne3][nm3][nmp] %= MOD;
                }
            }
        }
    }
    for (int e3 = 0; e3 < 2; e3++) for (int m3 = 0; m3 < 3; m3++) {
        for (int mod = 1; mod < P; mod++) for (int big = 0; big < 2; big++) (memo[0][e3][m3] += memo1[5][big][e3][m3][mod]) %= MOD;
    }
    // memo2 を求める
    memo2[0][0][0][0] = 1;
    for (int i = 0; i < 5; i++) for (int e3 = 0; e3 < 2; e3++) {
        for (int m3 = 0; m3 < 3; m3++) for (int mp = 0; mp < P; mp++) {
            for (int j = 0; j < 10; j++) {
                int nm3 = (m3+j)%3, nmp = (mp*10+j)%P;
                int ne3 = e3;
                ne3 |= (j==3);
                memo2[i+1][ne3][nm3][nmp] += memo2[i][e3][m3][mp];
                memo2[i+1][ne3][nm3][nmp] %= MOD;
            }
        }
    }
    for (int e3 = 0; e3 < 2; e3++) for (int m3 = 0; m3 < 3; m3++) {
        for (int mod = 1; mod < P; mod++) (memo[1][e3][m3] += memo2[5][e3][m3][mod]) %= MOD;
    }
    // dp を求める
    dp[0][0][0][0] = 1;
    for (int i = 0; i < n-5; i++) for (int big = 0; big < 2; big++) {
        for (int e3 = 0; e3 < 2; e3++) for (int m3 = 0; m3 < 3; m3++) {
            if (big) {
                for (int j = 0; j < 10; j++) {
                    int nm3 = (m3+j)%3;
                    int ne3 = e3;
                    ne3 |= (j==3);
                    dp[i+1][big][ne3][nm3] += dp[i][big][e3][m3];
                    dp[i+1][big][ne3][nm3] %= MOD;
                }
            } else {
                int num = s[i]-'0';
                for (int j = 0; j <= num; j++) {
                    int nm3 = (m3+j)%3;
                    int ne3 = e3;
                    ne3 |= (j==3);
                    int nbig = (j<num);
                    dp[i+1][nbig][ne3][nm3] += dp[i][big][e3][m3];
                    dp[i+1][nbig][ne3][nm3] %= MOD;
                }
            }
        }
    }
    ll ans = 0;
    for (int big = 0; big < 2; big++) {
        for (int e3 = 0; e3 < 2; e3++) {
            for (int m3 = 0; m3 < 3; m3++) {
                if (!e3) {
                    ans += dp[n-5][big][e3][m3] * memo[big][0][(3-m3)%3] % MOD;
                    for (int j = 0; j < 3; j++) {
                        ans += dp[n-5][big][e3][m3] * memo[big][1][j] % MOD;
                    }
                } else {
                    for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) {
                        ans += dp[n-5][big][e3][m3] * memo[big][i][j] % MOD;
                    }
                }
                ans %= MOD;
            }
        }
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string A, B;
    int P;
    cin >> A >> B >> P;
    ll ans = calc(B, P)-calc(A, P)+check(A, P);
    ans = (ans%MOD + MOD) % MOD;
    cout << ans << endl;
    return 0;
}
0