Kummer定理-超级Lucas定理-数论-组合数学-学习笔记

· · 个人记录

做寒假作业时发现自己啥都不会...

Kummer定理

设m，n为正整数，p为素数，则C^n_{n+m}含p的幂次等于m+n在p进制下的进位次数

证明：

来一道题：求\sum \limits_{i=0}^n [C^i_n \mod 4=0]

我们用总数减去不符合规定的数量：进位0次或1次的。我们可以枚举进位的位置。

一道类似的题，求9的倍数：

例题：CF582D

好恶心啊...不想写

题意：

给出一个质数 p 和一个数 a，和一个大整数 A，求有多少对 n、m 满足 0≤m≤n≤A，且 p^a∣C^n_m。

也就是C^n_m中p的幂次\ge a，也就是设a=m-n,b=n，求a+b\le A,a+b的p进制进位次数\ge a的数量。

我们可以数位DP来求（我们DP的是a+b的值）

设f(i,j,k,eq)表示考虑了前i位，已经进位j次，第i+1位是否要向前进位，是否可以任意填的方案数。

转移的话，系数是一个等差数列，写几个找找规律即可。

il int calcS(int n,int up,int ex)
{
    if(!up) return sub((LL)(n+2)*(n+1)/2%md,ex*(n+1));
    else return add((LL)(p-1+p-1-n)*(n+1)/2%md,ex*(n+1));
}
il int calcP(int n,int up,int ex)
{
    if(!up) return n+1-ex;
    else return p-1-n+ex;
}
    f[0][0][0][1]=1;
    for(ri i=1; i<=n; ++i)
        for(ri j=0; j<=a; ++j)
            for(ri k=0; k<=1; ++k)
                for(ri eq=0; eq<=1; ++eq)
                {
                    int t=f[i-1][j][k][eq];
                    if(!t) continue;
                    for(ri up=0; up<=1; ++up)
                    {
                        int nj=min(j+up,a);
                        if(!eq) inc(f[i][nj][up][0],mul(t,calcS(p-1,k,up)));
                        else
                        {
                            inc(f[i][nj][up][1],mul(t,calcP(A[i],k,up)));
                            if(A[i]) inc(f[i][nj][up][0],mul(t,calcS(A[i]-1,k,up)));
                        }
                    }
                }