bzoj 4737: 组合数问题

时间：2021-10-24 16:51:43

Description

组合数C(n,m)表示的是从n个物品中选出m个物品的方案数。举个例子，从(1,2,3)三个物品中选择两个物品可以有(

1,2),(1,3),(2,3)这三种选择方法。根据组合数的定义，我们可以给出计算组合数C(n,m)的一般公式：
C(n,m)=n!/m!*(n?m)!
其中n!=1×2×?×n。（额外的，当n=0时，n!=1）
小葱想知道如果给定n,m和k，对于所有的0≤i≤n，0≤j≤min(i,m)有多少对(i,j)满足C(i,j)是k的倍数。

Input

第一行有两个整数t,k，其中t代表该测试点总共有多少组测试数据，k的意义见。
接下来t行每行两个整数n,m，其中n,m的意义见。

Output

t行，每行一个整数代表所有的0≤i≤n，0≤j≤min(i,m)中有多少对(i,j))满足C(i,j)是k的倍数

答案对10^9+7取模。

由lucas定理的推论，C(i,j)不是k的倍数当且仅当k进制下i的每一位分别>=j

先补上前导零使n,m位数相同从高位到低位进行数位dp，f[i][0/1][0/1]表示当前已决策高于第i位的部分，已决策部分是否与n,m相等，满足条件的方案数。

#include<cstdio>

#include<cstring>

const int P=;

typedef long long i64;

int T,k,ns[],ms[],f[][][];

i64 n,m;

int min(int a,int b){return a<b?a:b;}

int max(int a,int b){return a>b?a:b;}

i64 S(i64 x){return x%=P,x*(x+)/%P;}

i64 cal(i64 a,i64 b){

    if(a<b)b=a;

    return (S(a)-S(a-b))%P;

}

i64 s[][];

int main(){

    scanf("%d%d",&T,&k);

    for(int i=;i<=k;++i)

    for(int j=;j<=k;++j)s[i][j]=cal(i,j);

    for(;T;--T){

        scanf("%lld%lld",&n,&m);

        if(n<m)m=n;

        int ans=cal(n+,m+);

        int np=,mp=;

        while(n)ns[++np]=n%k,n/=k;

        while(m)ms[++mp]=m%k,m/=k;

        while(mp<np)ms[++mp]=;

        memset(f,,sizeof(f));

        f[np][][]=;

        for(int i=np;i;--i){

            int(*F)[]=f[i],(*G)[]=f[i-];

            int vn=ns[i],vm=ms[i];

            G[][]=F[][]*(vn>=vm);

            G[][]=(F[][]*i64(vn+)+F[][]*(i64)min(vn+,vm))%P;

            G[][]=(F[][]*i64(k-vm)+F[][]*(i64)max(vn-vm,))%P;

            G[][]=(F[][]*s[k][k]+F[][]*s[k][vm]+F[][]*s[vn][k]+F[][]*s[vn][vm])%P;

        }

        for(int a=;a<;++a)

        for(int b=;b<;++b)

        ans=(ans-f[][a][b])%P;

        printf("%d\n",(ans+P)%P);

    }

    return ;

}

相关文章