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
AC × 5
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