Submission #1613598

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7;
const int MAX_N=10000;
int d;
string s;
ll dp[100010][2][100];
int tmp[10010][110];

int main(){
	cin >> d >> s;
	
	dp[0][0][0]=1;
	REP(i,0,s.size()) REP(j,0,2) REP(k,0,d){
		int n=(j?10:s[i]-'0'+1);
		
		REP(l,0,n){
			dp[i+1][j|(l+1)<n][(k+l)%d] += dp[i][j][k];
			dp[i+1][j|(l+1)<n][(k+l)%d] %= MOD;
		}
	}

	cout << (dp[s.size()][0][0]+dp[s.size()][1][0]-1+MOD)%MOD << endl;
	return 0;
}
	

Submission Info

Judge Result