結果

問題 No.372 It's automatic
コンテスト
ユーザー norioc
提出日時 2026-01-05 14:48:50
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3,529 ms / 6,000 ms
コード長 1,568 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,342 ms
コンパイル使用メモリ 341,112 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-05 14:49:39
合計ジャッジ時間 44,789 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

static const long long MOD = 1000000007;

int main() {
    string S;
    int M;
    cin >> S >> M;

    // state:
    // 0 = 未選択
    // 1 = 長さ1（'0'）
    // 2 = 長さ1（'1'〜'9'）
    // 3 = 長さ2以上（先頭非0）
    vector<vector<long long>> dp(4, vector<long long>(M, 0));
    dp[0][0] = 1;

    for (char c : S) {
        int x = c - '0';
        auto ndp = dp; // 使わない遷移

        for (int st = 0; st < 4; st++) {
            for (int m = 0; m < M; m++) {
                long long v = dp[st][m];
                if (v == 0) continue;

                if (st == 0) {
                    // 初めて選ぶ
                    if (x == 0)
                        ndp[1][0] = (ndp[1][0] + v) % MOD;
                    else
                        ndp[2][x % M] = (ndp[2][x % M] + v) % MOD;
                }
                else if (st == 1) {
                    // "0" の後に何か付ける → 先頭0の長さ>=2 → 禁止
                    continue;
                }
                else if (st == 2 || st == 3) {
                    // 先頭非0が保証されている
                    int nm = (m * 10 + x) % M;
                    ndp[3][nm] = (ndp[3][nm] + v) % MOD;
                }
            }
        }

        dp.swap(ndp);
    }

    long long ans = 0;
    // 長さ1（"0" も含む）
    ans = (ans + dp[1][0]) % MOD;
    ans = (ans + dp[2][0]) % MOD;
    // 長さ2以上
    ans = (ans + dp[3][0]) % MOD;

    cout << ans << '\n';
    return 0;
}
0