AT_tdpc_number 数 题解
cq_zry
·
·
题解
分析
明显能用记忆化搜索来进行数位 DP。
【如何搜索】
我们记录 \mathit{f}_{i,j} 表示若搜索到第 i 位，前面对于 D 取模的话，答案的个数。然后按照模板写即可，在搜索完时，只要余数是零，就表示这个数对于 d 取模之后的值为 0。
为什么可以按位取模？因为：(a_1+a_2+a_3) \bmod d=
((((a_1 \bmod d)+a_2)\bmod d)+a_3) \bmod d。
【如何输入】
**【注意事项】**
要对 $10^9+7$ 进行取模，能取模的尽量取模。同时，这个题有点古老，所以……输出换行！（我没输出换行交了 $2$ 页 pwp）
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1000000007;
const int N=10001,M=101;
int p;
string n;
int a[N],len;
int f[N][M];
inline int dfs(int now_where,int md,bool if_le,int p)
{
if(now_where==0) return !md;
else if(!if_le&&f[now_where][md]!=-1) return (f[now_where][md]+MOD)%MOD;
else
{
int ans=0,up=if_le?a[now_where]:9;
for(int i=0;i<=up;i++)
ans=(ans+dfs(now_where-1,(md+i)%p,if_le&&i==up,p)+MOD)%MOD;//按位增加再取模
return if_le?((ans+MOD)%MOD):f[now_where][md]=((ans+MOD)%MOD);
}
}
inline int check(string s,int p)
{
memset(f,-1,sizeof(f));
len=0;
for(int i=s.size()-1;i>=0;i--)
a[++len]=s[i]-'0';
return dfs(len,0,1,p);
}
signed main()
{
cin>>p>>n;
return printf("%lld\n",check(n,p)-check("0",p)),0;
}
```