結果

問題 No.1417 100の倍数かつ正整数(2)
ユーザー MisterMister
提出日時 2021-03-05 21:34:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 3,000 ms
コード長 1,635 bytes
コンパイル時間 816 ms
コンパイル使用メモリ 85,576 KB
最終ジャッジ日時 2025-01-19 10:41:42
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "main.cpp"
#include <atcoder/modint>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
using mint = atcoder::modint1000000007;

void solve() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());

    auto dp = vector(2, vector(3, vector(3, mint(0))));
    dp[0][0][0] = dp[1][0][0] = 1;

    mint ans = 0;
    for (auto ci : s) {
        ans += dp[0][2][2];

        int c = ci - '0';

        auto ndp = vector(2, vector(3, vector(3, mint(0))));
        for (int d = 1; d <= 9; ++d) {
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    int ni = i, nj = j;
                    {
                        int x = d;
                        while (x % 2 == 0) {
                            x /= 2;
                            ++ni;
                        }
                        while (x % 5 == 0) {
                            x /= 5;
                            ++nj;
                        }

                        ni = min(ni, 2);
                        nj = min(nj, 2);
                    }

                    // all -> all
                    ndp[0][ni][nj] += dp[0][i][j];

                    // all -> sub
                    if (d < c) ndp[1][ni][nj] += dp[0][i][j];

                    // sub -> sub
                    if (d == c) ndp[1][ni][nj] += dp[1][i][j];
                }
            }
        }

        swap(dp, ndp);
    }

    ans += dp[1][2][2];
    cout << ans.val() << "\n";
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    solve();

    return 0;
}
0