【Codeforces】 CF582D Number of Binominal Coefficients

题目链接

CF方向
Luogu方向

题目解法

看到 $p^{\alpha }|(\genfrac{}{}{0ex}{}{n}{k})$ ，首先想到 $kummer$ 定理，那么限制即为 $n-k$ 和 $k$ 做加法在 $p$ 进制下的进位数 $\ge \alpha$
然后就是一个显然的数位 $dp$ 了
因为进位从前往后数位 $dp$ 不太好考虑，所以我们考虑从后往前做，然后多记录一维 $0/1/2$
我的状态是 $f_{i,j,0/1,0/1/2}$ 表示后 $i$ 位有 $j$ 个进位（不包括第 $i$ 位的），这一位是否进位，后面 $i$ 位 $n$ 与 $A$ 的关系（0 表示 $n<A$，1 表示 $n=A$，2 表示 $n>A$）
因为我们把 $n,k$ 变成了 $n-k$ 和 $k$，所以天然保证了 $n\ge k$，不需要考虑 $n,k$ 的大小关系
直接 $dp$ 即可，实现的有些烦，但也不知道可以优化什么了
时间复杂度 $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4100,P=1e9+7;
int p,a,f[2][N][2][3];
LL A[N],B[N];
// int g[P];//g[i]表示a+b<=i的方案数(a,b无序)
char str[N];
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
inline void inc(int &x,LL y){ x=(x+y)%P;}
int g(int x){
    if(x<0) return 0;
    if(x<p) return (1ll*(x+2)*(x+1)/2)%P;
	x=p*2-1-x;x=1ll*p*p%P-(1ll*x*(x-1)/2)%P;
	return x<0?x+P:x;
}
int main(){
    p=read(),a=read();
    scanf("%s",str+1);
    int len=strlen(str+1);
    for(int i=1;i<=len;i++) A[i]=str[len-i+1]-48;
    int n=0;
    for(int i=len;i>=1;i--){
        for(int j=1;j<N;j++) B[j]*=10;
        B[1]+=A[i];
        for(int j=1;j<N;j++) if(B[j]>=p) B[j+1]+=B[j]/p,B[j]%=p;
    }
    for(int i=1;i<N;i++) A[i]=B[i];
    for(int i=1;i<N;i++) if(A[i]) n=i;
    reverse(A+1,A+n+1);
    f[(n+1)&1][0][0][1]=1;
    for(int i=n+1;i>1;i--){
        int c=A[i-1];
        int g_c=g(c);
        int g_c_1=g(c-1);
        int g_c_2=g(c-2);
        int g_p_1=g(p-1);
        int g_p_2=g(p-2);
        int g_p_c=g(p+c);
        int g_p_c_1=g(p+c-1);
        int g_p_c_2=g(p+c-2);
        int g_2p_2=g(p*2-2);
        int g_2p_3=g(p*2-3);
        memset(f[~i&1],0,sizeof(f[~i&1]));
        for(int j=0;j<=n-i+1;j++){
            //calc f[~i&1][j][0][0]
            inc(f[~i&1][j][0][0],1ll*f[i&1][j][0][0]*g_c);
            if(c){
                for(int t:{1,2}) inc(f[~i&1][j][0][0],1ll*f[i&1][j][0][t]*g_c_1);
                if(j){
                    inc(f[~i&1][j][0][0],1ll*f[i&1][j-1][1][0]*g_c_1);
                    if(c>1) for(int t:{1,2}) inc(f[~i&1][j][0][0],1ll*f[i&1][j-1][1][t]*g_c_2);
                }
            }
            //calc f[~i&1][j][0][1]
            if(!c) inc(f[~i&1][j][0][1],1ll*f[i&1][j][0][1]*g_c);
            else inc(f[~i&1][j][0][1],1ll*f[i&1][j][0][1]*(g_c-g_c_1+P));
            if(j&&c) inc(f[~i&1][j][0][1],1ll*f[i&1][j-1][1][1]*(g_c_1-g_c_2+P));
            //calc f[~i&1][j][0][2]
            for(int t:{0,1}) inc(f[~i&1][j][0][2],1ll*f[i&1][j][0][t]*(g_p_1-g_c+P));
            inc(f[~i&1][j][0][2],1ll*f[i&1][j][0][2]*(g_p_1-g_c_1+P));
            if(j){
                for(int t:{0,1}) inc(f[~i&1][j][0][2],1ll*f[i&1][j-1][1][t]*(g_p_2-g_c_1+P));
                inc(f[~i&1][j][0][2],1ll*f[i&1][j-1][1][2]*(g_p_2-g_c_2+P));
            }
            //calc f[~i&1][j][1][0]
            inc(f[~i&1][j][1][0],1ll*f[i&1][j][0][0]*(g_p_c-g_p_1+P));
            for(int t:{1,2}) inc(f[~i&1][j][1][0],1ll*f[i&1][j][0][t]*(g_p_c_1-g_p_1+P));
            if(j){
                inc(f[~i&1][j][1][0],1ll*f[i&1][j-1][1][0]*(g_p_c_1-g_p_2+P));
                for(int t:{1,2}) inc(f[~i&1][j][1][0],1ll*f[i&1][j-1][1][t]*(g_p_c_2-g_p_2+P));
            }
            //calc f[~i&1][j][1][1]
            inc(f[~i&1][j][1][1],1ll*f[i&1][j][0][1]*(g_p_c-g_p_c_1+P));
            if(j) inc(f[~i&1][j][1][1],1ll*f[i&1][j-1][1][1]*(g_p_c_1-g_p_c_2+P));
            //calc f[~i&1][j][1][2]
            for(int t:{0,1}) inc(f[~i&1][j][1][2],1ll*f[i&1][j][0][t]*(g_2p_2-g_p_c+P));
            inc(f[~i&1][j][1][2],1ll*f[i&1][j][0][2]*(g_2p_2-g_p_c_1+P));
            if(j){
                for(int t:{0,1}) inc(f[~i&1][j][1][2],1ll*f[i&1][j-1][1][t]*(g_2p_2-g_p_c_1+P));
                inc(f[~i&1][j][1][2],1ll*f[i&1][j-1][1][2]*(g_2p_2-g_p_c_2+P));
            }
        }
    }
    int ans=0;
    for(int i=a;i<=n;i++) inc(ans,1ll*f[1][i][0][0]+f[1][i][0][1]);
    printf("%d\n",ans);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}
/*
f[i][j][0/1][0/1/2]:到第i位，后j位已经填好且进位了j次，这一位是否进位，n后面j位和A的关系(0小于，1等于，2大于)
*/