Submission #5546905
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MOD=1e9+7; const int INF=1e9; int dp[100001][2][100]; int main(){ int D; string N; cin>>D>>N; int l=N.size(); dp[0][0][0]=1; for(int i=0;i<l;i++){ int A=N[i]-'0'; for(int j=0;j<2;j++){ for(int k=0;k<D;k++){ for(int a=0;a<=(j?9:A);a++){ dp[i+1][j||a<A][(k+a)%D]+=dp[i][j][k]; dp[i+1][j||a<A][(k+a)%D]%=MOD; } } } } cout<<((dp[l][0][0]+dp[l][1][0])%MOD+MOD-1)%MOD<<endl; }
Submission Info
Submission Time | |
---|---|
Task | E - 数 |
User | koikuchi |
Language | C++14 (GCC 5.4.1) |
Score | 4 |
Code Size | 629 Byte |
Status | AC |
Exec Time | 90 ms |
Memory | 8448 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 | 2 ms | 256 KB |
01 | AC | 56 ms | 8448 KB |
02 | AC | 90 ms | 8448 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |