首先你得知道什么是库默尔定理：
对于 (nn+m) 和一个质数 p ，存在一个最大的 a 使得 pa|(nn+m) ，有 a=f(n+m,p) ，其中 f(a,b) 表示 a 在 b 进制下的进位次数。
于是可以数位 DP 出所有合法的 n+m ，然后计算方案数。
设 dp(i,0/1,0/1,j) ，表示做到了从高到低第 i 位，这 i 位是否均达到上限，第 i+1 位 (比 i 低一位) 是否向 i 进位，到目前为止一共进位了 j 次的方案数。
转移时乘上这一位新增的数分配给 n,m 的方案数即可。
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=3.5e3+5;
const int mod=1e9+7;
ll res[N+5];
int P,L,n,num[N],f[2][2][N],g[2][2][N];
char str[N];
namespace _ {
inline int mul(int x,int y) {return 1ll*x*y%mod;}
inline int del(int x,int y) {x-=y;if(x<0) x+=mod;return x;}
inline int add(int x,int y) {x+=y;if(x>=mod) x-=mod;return x;}
inline void inc(int&x,int y) {x+=y;if(x>=mod) x-=mod;}
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
}using namespace _;
inline void pre() {
IN(P),IN(L),scanf("%s\n",str+1),n=strlen(str+1);
if(!P) {puts("0");exit(0);}
for(int i=1;i<=n;++i) num[i]=str[n-i+1]-'0';
for(int i=n;i>=1;--i) {
for(int j=1;j<N;++j) res[j]*=10;
res[1]+=num[i];
for(int j=1;j<N;++j) if(res[j]>=P) res[j+1]+=res[j]/P,res[j]%=P;
}
for(int i=1;i<(n=N);++i) num[i]=res[i];
while(n&&!num[n-1]) --n;
}
int main() {
pre();
f[1][0][0]=1;
for(int i=n-1;i;--i) {
int t0=(ll)P*(P+1)/2%mod;
int t1=(ll)P*(P-1)/2%mod;
int t2=(ll)num[i]*(num[i]+1)/2%mod;
int t3=(ll)num[i]*(num[i]-1)/2%mod;
int t4=(ll)num[i]*(P+P-num[i]-1)/2%mod;
int t5=(ll)num[i]*(P+P-num[i]+1)/2%mod;
memset(g,0,sizeof(g));
for(int j=0;j<n-i;++j) {
int f0=f[0][0][j],f1=f[0][1][j],f2=f[1][0][j],f3=f[1][1][j];
inc(g[0][0][j],add(mul(f0,t0),mul(f2,t2)));
inc(g[0][1][j],add(mul(f0,t1),mul(f2,t3)));
inc(g[1][0][j],mul(f2,num[i]+1)),
inc(g[1][1][j],mul(f2,num[i])),
inc(g[0][0][j+1],add(mul(f1,t1),mul(f3,t4))),
inc(g[0][1][j+1],add(mul(f1,t0),mul(f3,t5))),
inc(g[1][0][j+1],mul(f3,P-num[i]-1)),
inc(g[1][1][j+1],mul(f3,P-num[i]));
}
swap(f,g);
}
int ans=0;
for(int i=L;i<=n;++i) inc(ans,add(f[0][0][i],f[1][0][i]));
printf("%d\n",ans);
return 0;
}
C++
0 条评论