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 |
|
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 |