【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大于)
*/