Submission #447917

---

Source Code Expand

#include <algorithm>
#include <array>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <ostream>
#include<complex>
#include <cmath>
#include <iostream>
#include <stack>
#include <fstream>
#include <queue>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <bitset>
#include <iomanip>
#include <string>
#include <vector>
#include <string>
using namespace std;
#define OB (bitset<32>)
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define ALLOF(c) begin(), (c),end()
typedef long long ll;

#define PI 3.141592653589793
#define EPS 0.0000001
#define MOD 1000000007
int main()
{ 
    int d;
    string n;
    int dp[10001][100];
    int ans = 0;
    int sum_ketatop = 0;
    cin >> d >> n;
    fill(*dp,*dp + 10000*100,0);
    //fill(*ans,*ans + 10000*100,0);
    dp[0][0] = 1;
    rep(i,10)
    {
        dp[1][i % d] += 1;
    }
    REP(i,1,n.length())
    {
        rep(j,max(10,d))
        {
            rep(k,10)
            {
                dp[i+1][(j+k) % d] = (dp[i+1][(j+k)% d] + dp[i][j]) % MOD ;
            }
        }
    }

    rep(i,n.length()-1)
    {
        int top = n[i]-'0';  
        rep(j,top)
        {    
            ans += dp[n.length()-i-1][(2*d-sum_ketatop - j) % d];
            ans %= MOD;     
        }
        sum_ketatop += top;
        sum_ketatop %= d;
    }
    rep(i,n[n.length()-1] - '0' + 1)
    {
        if ((2*d-sum_ketatop - i ) % d ==  0)
        {
            ans++;
        }
    }
    ans -= 1;// remove a = 0;
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result