Typical DP Contest

Submission #6349320

Source codeソースコード

#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

Task問題 E - 数
User nameユーザ名 jimmy
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 4
Source lengthソースコード長 1706 Byte
File nameファイル名
Exec time実行時間 154 ms
Memory usageメモリ使用量 15872 KB

Test case

Set

Set name Score得点 / Max score Cases
All 4 / 4 00,01,02,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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