【Codeforces 582D】Number of Binominal Coefficients | Mrsrz's blog

数位 DP。

题目大意：

给定质数 $p$ 和 整数 $\alpha$，大整数 $A$，求有多少对 $n,k$ 满足 $0\leq k\leq n\leq A$ 且 $p^\alpha|\binom{n}{k}$。

题解：

我们考虑如何求 $\binom{n}{m}$ 中含有的质因子 $p$ 个数。

$$cnt=\sum_{i=1}^\infty \lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor-\lfloor\frac{n-m}{p^i}\rfloor$$

不难发现，对每个 $i$，它对质因子个数的贡献只可能为 $0$ 或 $1$。

而是否产生贡献，取决于 $m$ 和 $n-m$ 在 $p$ 进制下做加法的第 $i$ 位是否进位。

于是，我们先将 $A$ 转化为 $p$ 进制，然后进行数位 DP 即可。

令 $f[n][m][0/1][0/1]$ 表示当前考虑到第 $n$ 位，之前已经进位 $m$ 次，前面考虑的位是否紧贴上界，最后考虑的这位是否需要从下一位进 $1$。

然后转移分一些情况讨论即可。

最后对于进位次数大于等于 $\alpha$ 且最低位不进位的方案求和即可。

时间复杂度 $O(|A|^2)$。

Code：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=5005,md=1e9+7;
int p,alpha,n;
int A[N],ans;
inline void add(int&a,const LL&b){a=(a+b)%md;}
void Read(){
    char s[N],t[N];
    scanf("%s",s);
    int lens=strlen(s);
    for(int i=0;i<lens;++i)s[i]^='0';
    while(1){
        LL d=0;int lent=0;
        for(int i=0;i<lens;++i){
            d=d*10+s[i];
            t[lent++]=d/p,d-=d/p*p;
        }
        int beg=0;
        while(t[beg]==0&&beg<lent)++beg;
        A[n++]=d;
        if(lent==beg)return;
        for(int i=beg;i<lent;++i)
        s[i-beg]=t[i];
        lens=lent-beg;
    }
}
int f[2][N][2][2];
int a1,a2,a3,a4;
inline int calc(int x){
    if(x<p)return(x+1LL)*(x+2)/2%md;
    return(a1-calc(2*p-3-x)+md)%md;
}
void calc(){
    a1=(LL)p*p%md,a3=calc(p-1),a2=(a1-a3+md)%md,a4=calc(p-2);
    f[0][0][0][0]=calc(A[0]-1);
    f[0][1][0][1]=calc(A[0]-2);
    f[0][0][1][0]=A[0]+1;
    f[0][1][1][1]=A[0];
    for(int i=1;i<n;i++){
        memset(f[i&1],0,sizeof*f);
        for(int c=0;c<=alpha;++c){
            const int t=min(c+1,alpha);
            const int&P=f[i&1^1][c][0][0];
            add(f[i&1][c][0][0],(LL)P*a3);
            add(f[i&1][t][0][1],(LL)P*a4);
            const int&Q=f[i&1^1][c][0][1];
            add(f[i&1][c][0][0],(LL)Q*(a1-a3+md));
            add(f[i&1][t][0][1],(LL)Q*(a1-a4+md));
            const int&X=f[i&1^1][c][1][0];
            add(f[i&1][c][0][0],(LL)X*calc(A[i]-1));
            add(f[i&1][t][0][1],(LL)X*calc(A[i]-2));
            add(f[i&1][c][1][0],(LL)X*(A[i]+1));
            add(f[i&1][t][1][1],(LL)X*A[i]);
            const int&Y=f[i&1^1][c][1][1];
            add(f[i&1][c][0][0],(LL)Y*(calc(A[i]+p-1)-a3+md));
            add(f[i&1][t][0][1],(LL)Y*(calc(A[i]+p-2)-a4+md));
            add(f[i&1][c][1][0],(LL)Y*(p-A[i]-1));
            add(f[i&1][t][1][1],(LL)Y*(p-A[i]));
        }
    }
    ans=(f[n&1^1][alpha][0][0]+f[n&1^1][alpha][1][0])%md;
}
int main(){
    scanf("%d%d",&p,&alpha);
    if(alpha>5000)return puts("0")&0;
    Read();
    reverse(A,A+n);
    calc();
    printf("%d\n",ans);
    return 0;
}