Submission #6349320


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,N) for(ll i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

string n;
int d;
ll dp[10001][100][2];

int main(){
    cin >> d >> n;
    dp[0][0][0] = 1;
    rep(i,n.size()){
        rep(j,d){
            rep(k,10){
                if(k == n[i] - '0'){
                    dp[i+1][(j+k)%d][0] += dp[i][j][0];
                    dp[i+1][(j+k)%d][0] %= MOD;
                    dp[i+1][(j+k)%d][1] += dp[i][j][1];
                    dp[i+1][(j+k)%d][1] %= MOD;
                }
                else if(k > n[i] - '0'){
                    dp[i+1][(j+k)%d][1] += dp[i][j][1];
                    dp[i+1][(j+k)%d][1] %= MOD;
                }
                else{
                    dp[i+1][(j+k)%d][1] += dp[i][j][0];
                    dp[i+1][(j+k)%d][1] %= MOD;
                    dp[i+1][(j+k)%d][1] += dp[i][j][1];
                    dp[i+1][(j+k)%d][1] %= MOD;
                }
            }
        }
    }
    cout << ((dp[n.size()][0][0] + dp[n.size()][0][1]) % MOD - 1 + MOD)%MOD << endl;
}

Submission Info

Submission Time
Task E - 数
User jimmy
Language C++14 (GCC 5.4.1)
Score 4
Code Size 1706 Byte
Status AC
Exec Time 154 ms
Memory 15872 KB

Judge Result

Set Name All
Score / Max Score 4 / 4
Status
AC × 5
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 3 ms 384 KB
01 AC 94 ms 15872 KB
02 AC 154 ms 15744 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB