-
Notifications
You must be signed in to change notification settings - Fork 0
/
DigitSum.cpp
49 lines (48 loc) · 1020 Bytes
/
DigitSum.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Seek Knowledge from the cradle to the grave
// Author : Syed Mujtaba Hadi Jafri
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[100004][104][2];
signed main()
{
string k;
int d, ans = -1;
int mod = 1e9 + 7;
cin >> k >> d;
vector < int > dig;
for(auto z : k)
dig.push_back(z - '0');
reverse(dig.begin(), dig.end());
int n = dig.size();
for(int i = 0; i < d; i++) // Base Case
{
for(int j = 0; j <= 9; j++)
{
if((j + i)%d == 0)
dp[0][i][0]++;
if(j <= dig[0])
if((j + i)%d == 0)
dp[0][i][1]++;
}
}
for(int i = 1; i < n; i++)
{
for(int j = 0; j < d; j++)
{
for(int z = 0; z <= 9; z++)
{
dp[i][j][0] = (dp[i][j][0]%mod + dp[i - 1][(j + z)%d][0]%mod)%mod;
if(z < dig[i])
{
dp[i][j][1] = (dp[i][j][1]%mod + dp[i - 1][(j + z)%d][0]%mod)%mod;
}
if(z == dig[i])
{
dp[i][j][1] = ((dp[i][j][1])%mod + (dp[i - 1][(j + z)%d][1])%mod)%mod;
}
}
}
}
cout << (dp[n - 1][0][1] - 1 + mod)%mod<< endl;
}