[HDU6372]Lucas

Link

Solution

根据Lucas Theorem,\binom{n}{m}\mod p=0\Leftrightarrow np进制表示的每一位都\ge mp进制表示的对应位。
对于题目中的np进制数字iHMBB[i][j]=1j的个数就是满足如上条件的j的个数,HMBB的一次方中的1的个数就是p^n-1\ge i\ge j(i,j)数(此处的\ge指每位对应\ge
同理,HMBB^k1的个数就是p^n-1\ge a_1\ge a_2\ge…\ge a_{k+1}的个数。
而每一位是独立的,可以单独计算一位的然后求个幂。
而一位的答案就是以p-1为开头,长度为k+2的不升序列的长度。用组合数计算,可以假设开头再放上一个0,那么就是开头为0,结尾p-1,中间k+1个数的非降序列数。除去开头,后面k+2个数每个数字相对于前面的数字的增量\ge 0,且总的增量为p-1,因此对于增量列出方程

\left\{\begin{aligned}
\sum \Delta_i=&p-1\\
\Delta_i \ge&0
\end{aligned}\right.

方案数为\binom{(p-1)+(k+1)}{k+1}
最终要计算的就是

\begin{aligned}
&\sum_{i=1}^{k}\sum_{j=1}^n \binom{p+i}{i+1}^j
\end{aligned}

Code

#include <bits/stdc++.h>

const int N=2e6,XN=N+11,P=1e9+7;

void M(int &x) {
    ((x>=P) && (x-=P)) || ((x<0) && (x+=P));
}

int Pow(long long base,int v,int P) {
    long long res=1;
    for(;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0) {
                break;
            } 
        }
    }
}

int fact[XN],ifact[XN];
int C(int n,int m) {
    return n>=m?1ll*fact[n]*ifact[m]%P*ifact[n-m]%P:0;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);

//  freopen("input","r",stdin);

    fact[0]=1;
    for(int i=1;i<=N;++i)
        fact[i]=1ll*fact[i-1]*i%P;
    ifact[N]=Pow(fact[N],P-2,P);
    for(int i=N-1;i>=0;--i)
        ifact[i]=1ll*ifact[i+1]*(i+1)%P;

    Prep();
    int T;std::cin>>T;
    while(T--) {
        int c,n,k;std::cin>>c>>n>>k;
        int p=prime[c];
        int Ans=0;
        for(int i=1;i<=k;++i) {
            int v=C(p+i,i+1);
            M(Ans+=v==1?v*n%P:1ll*v*(1ll-Pow(v,n,P))%P*Pow(1-v,P-2,P)%P);
        }
        std::cout<<Ans<<'\n';
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注