【题解】Number of Binominal Coefficients 数位 DP CF582D —Qiuly

首先你得知道什么是库默尔定理：

对于 $n\choose n+m$ 和一个质数 $p$ ，存在一个最大的 $a$ 使得 $p^a|{n\choose n+m}$ ，有 $a=f(n+m,p)$ ，其中 $f(a,b)$ 表示 $a$ 在 $b$ 进制下的进位次数。

于是可以数位 $\rm{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;
}