题意
给定一个质数p和整数a,A。请计算有多少对
答案比较大,对 10^9+7 取余再输出。
1≤p,a≤10^9, p 是质数,0≤A<10^1000
分析
知道kummer定理后直接数位dp就好了。
设f[i,j,0/1,0/1]表示有多少个数对(x,y)从高到低做到第i位,进位了j次,x+y的前i位是否卡着A的上界,下一位是否必须要进位。
直接转移即可。
发现在51nod上刷cf的题时根本不用花点头盾去要数据,直接开题解去cf上,既能拿程序又能拿数据,还只用5点头盾,简直爽的不行。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=3505;
const int MOD=1000000007;
int p,m,a[N],v[N],f[N][N][2][2],len,tot,pre1,pre2;
char str[N];
void divi()
{
for (int i=len;i>=1;i--) v[i]=str[i]-'0';
while (1)
{
LL s=0,g=0;
for (int i=1;i<=len;i++)
{
s=g*10+v[i];
v[i]=s/p; g=s%p; } a[++tot]=g; int flag=0; for (int i=1;i<=len;i++) if (v[i]) {flag=1;break;} if (!flag) break; } } void updata(int &x,int y) { x+=y;x-=x>=MOD?MOD:0; } void solve() { f[tot+1][0][1][0]=1; for (int i=tot+1;i>1;i--) { int now=a[i-1],pre=(LL)now*(now+1)/2%MOD,pre_=(LL)now*(now-1)/2%MOD;
for (int j=0;j<=tot;j++)
{
if (f[i][j][0][0])
{
int w=f[i][j][0][0];
updata(f[i-1][j][0][0],(LL)w*pre1%MOD);
updata(f[i-1][j+1][0][1],(LL)w*pre2%MOD);
}
if (f[i][j][0][1])
{
int w=f[i][j][0][1];
updata(f[i-1][j][0][0],(LL)w*pre2%MOD);
updata(f[i-1][j+1][0][1],(LL)w*pre1%MOD);
}
if (f[i][j][1][0])
{
int w=f[i][j][1][0];
updata(f[i-1][j][1][0],(LL)w*(now+1)%MOD);
updata(f[i-1][j+1][1][1],(LL)w*now%MOD);
updata(f[i-1][j][0][0],(LL)w*pre%MOD);
if (now>1) updata(f[i-1][j+1][0][1],(LL)w*pre_%MOD);
}
if (f[i][j][1][1])
{
int w=f[i][j][1][1];
updata(f[i-1][j][1][0],(LL)w*(p-1-now)%MOD);
updata(f[i-1][j+1][1][1],(LL)w*(p-now)%MOD);
updata(f[i-1][j][0][0],(LL)w*(pre+(LL)(p-now-1)*now%MOD)%MOD);
updata(f[i-1][j+1][0][1],(LL)w*(pre+(LL)(p-now)*now%MOD)%MOD);
}
}
}
int ans=0;
for (int i=m;i<=tot+1;i++) updata(ans,f[1][i][1][0]),updata(ans,f[1][i][0][0]);
printf("%d",ans);
}
int main()
{
scanf("%d%d",&p,&m);
pre1=(LL)p*(p+1)/2%MOD;
pre2=(LL)p*(p-1)/2%MOD;
scanf("%s",str+1);
len=strlen(str+1);
divi();
solve();
return 0;
}