Codeforces

Luogu

分析

首先有一个定理：

${a+b\choose a}$ 质因数分解后 $p$ 的幂次等于 $p$ 进制下 $a+b$ 的进位次数。

于是可以把 $A$ 转成 $p$ 进制，然后考虑数位 DP。设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 位，进位 $j$ 次，第 $i-1$ 位是否向第 $i$ 位进位，$a+b$ 是否顶着 $A$ 的上界的方案数。

转移比较繁琐，具体可以看这里。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=4000;
const int mod=1e9+7;

int n,l,p,alpha,a[N],b[N]; char s[N];
int dp[N][N][2][2];

int main() {
    p=read(),alpha=read(); scanf("%s",s+1); l=strlen(s+1);
    for (int i=1;i<=l;++i) b[i]=s[l-i+1]-'0';
    while (l) {
        ll t=0;
        for (int i=l;i>0;--i) {
            t=t*10+b[i],b[i]=t/p,t%=p;
            if (!b[i]&&i==l) --l;
        }
        a[++n]=t;
    }
    dp[n+1][0][0][1]=1;
    for (int i=n;i;--i) {
        int c1=1ll*p*(p+1)/2%mod,
            c2=1ll*a[i]*(a[i]+1)/2%mod,
            c3=1ll*p*(p-1)/2%mod,
            c4=1ll*a[i]*(2*p-a[i]-1)/2%mod,
            c5=1ll*a[i]*(a[i]-1)/2%mod,
            c6=1ll*a[i]*(2*p-a[i]+1)/2%mod;
        for (int j=0;j<=n-i+1;++j) {
            int f0=dp[i+1][j][0][0],f1=dp[i+1][j][0][1],
                f2=dp[i+1][j][1][0],f3=dp[i+1][j][1][1];
            dp[i][j][0][0]=(1ll*c1*f0+1ll*c2*f1+1ll*c3*f2+1ll*c4*f3)%mod;
            dp[i][j][0][1]=(1ll*(a[i]+1)*f1+1ll*(p-a[i]-1)*f3)%mod;
            dp[i][j+1][1][0]=(1ll*c3*f0+1ll*c5*f1+1ll*c1*f2+1ll*c6*f3)%mod;
            dp[i][j+1][1][1]=(1ll*a[i]*f1+1ll*(p-a[i])*f3)%mod;
        }
    }
    int ans=0;
    for (int i=alpha;i<=n;++i) ans=(0ll+ans+dp[1][i][0][0]+dp[1][i][0][1])%mod;
    printf("%d\n",ans);
    return 0;
}