Submission #17516680


Source Code Expand

Copy
#include <bits/stdc++.h>
// #include <atcoder/all>

using namespace std;
using ll = long long;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1000000007;

template <typename T>
void print(const T &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

// 上からi桁目までで条件を満たす数の総数
// [i桁目まで][smaller][dで割った余り]
ll dp[10100][2][100];

int main()
{
    int d;
    string N;
    cin >> d >> N;
    vector<int> num;
    int n = N.size();
    for (char c : N)
        num.push_back(c - '0');

    dp[0][0][0] = 1;

    for (int i = 0; i < n; ++i)
    {
        for (int surp = 0; surp < d; ++surp)
        {
            // not small -> not small
            // dp[i + 1][0][surp] += dp[i][0][(surp + num[i]) % d];
            dp[i + 1][0][(surp + num[i]) % d] += dp[i][0][surp];
            dp[i + 1][0][(surp + num[i]) % d] %= MOD;

            // not small -> small
            for (int digit = 0; digit < num[i]; ++digit)
            {
                dp[i + 1][1][(surp + digit) % d] += dp[i][0][surp];
                dp[i + 1][1][(surp + digit) % d] %= MOD;
            }

            // small -> small
            for (int digit = 0; digit < 10; ++digit)
            {
                dp[i + 1][1][(surp + digit + d) % d] += dp[i][1][surp];
                dp[i + 1][1][(surp + digit + d) % d] %= MOD;
            }
        }
    }
    cout << (dp[n][0][0] + dp[n][1][0]) % MOD - 1 << endl;
    return 0;
}

Submission Info

Submission Time
Task E - 数
User tottokodaichans
Language C++ (GCC 9.2.1)
Score 4
Code Size 1625 Byte
Status
Exec Time 86 ms
Memory 19176 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
× 5
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 2 ms 3772 KB
01 61 ms 19176 KB
02 86 ms 19112 KB
90 5 ms 3412 KB
91 2 ms 3476 KB