P2822 组合数问题

传送门

思路：

　　利用公式： C( n,r ) = C( n-1,r ) + C( n-1,r-1 )

　　由此可以将计算 C( n,r ) 的过程化为加法来做。

　　可以看出，C( n,r ) 其实就是求杨辉三角的第 n 行、第 r 列上的数（行列从 0 开始）。

　　先 N暴力地预处理出杨辉三角的各个项，用前缀和记录每一项之前能被 k 整除的排列对数。

　　对于每次询问，只要 O(1) 的时间，就能输出答案。

Code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define lck_max(a,b) ((a)>(b)?(a):(b))

#define lck_min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

const int maxn=;

LL n,m,k,T,c[maxn][maxn],f[maxn][maxn];

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

inline void out(LL xs)

{

    if(!xs) {putchar(); return;}

    if(xs<) putchar('-'),xs=-xs;

    LL kr[],ls=;

    while(xs) kr[++ls]=xs%,xs/=;

    while(ls) putchar(kr[ls]+),ls--;

}

inline void work()

{

    c[][]=;

    for(LL i=;i<maxn;i++) c[i][]=;

    for(LL i=;i<maxn;i++)

        for(LL j=;j<=i;j++)

            c[i][j]=(c[i-][j]+c[i-][j-])%k;

    for(LL i=;i<maxn;i++)

    {

        for(LL j=;j<=i;j++)

        {

            f[i][j]=f[i-][j]+f[i][j-]-f[i-][j-];

            if(c[i][j]==) f[i][j]+=;

        }

        f[i][i+]=f[i][i];

    }

}

int main()

{

    freopen("problem.in","r",stdin);

    freopen("problem.out","w",stdout);

    T=read();k=read();

    work();

    while(T--)

    {

        n=read();m=read();

        m=lck_min(n,m);

        out(f[n][m]),putchar('\n');

    }

    fclose(stdin);

    fclose(stdout);

return ;

}