結果

問題 No.315 世界のなんとか3.5
ユーザー mayoko_
提出日時 2015-12-08 14:07:34
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0