【Codeforces】 CF582D Number of Binominal Coefficients

题目链接

题目解法

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

相关阅读:
五种常见的IO模型
解决安装CentOS5之后，vi不显示颜色的问题
基于Java毕业设计职业信息服务平台源码+系统+mysql+lw文档+部署软件
零代码即可将数据可视化应用到企业管理中
如何区分异动电动机和同步电动机
机器学习、深度学习、强化学习、迁移学习的关联与区别
Mac远程连接Windows 11
三个烂怂八股文，变成两个场景题，打得我一脸问号。
Starknet架构之Starknet state、State commitment
websocket实现实时变化图表内容

原文地址：https://blog.csdn.net/djx2021/article/details/134097187