$Noip2016/Luogu2822$ 组合数问题

$Luogu$

看这题题解的时候看到一个好可爱的表情(●'◡'●)ﾉ♥

$Sol$

首先注意到这题的模数是$k$.然而$k$并不一定是质数,所以不能用$C_n^m=frac{n!}{m!(n-m)!}$.

所以还要记得另外一个公式吖:$C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}$

于是可以预处理出所有的$C$,以及所有的前缀和.这样就可以$O(1)$查询了.

最后还要注意特判$m>n$的情况

$over$

$Code$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define il inline
#define Rg register
#define go(i,a,b) for(Rg int i=a;i<=b;++i)
#define yes(i,a,b) for(Rg int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
#define inf 2147483647
using namespace std;
il int read()
{
    Rg int x=0,y=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*y;
}
const int N=2010;
int T,k,n,m,c[N][N];
ll s[N][N];
il void init()
{
    c[1][1]=1;
    go(i,1,2000)c[i][0]=1;
    go(i,2,2000)
        go(j,1,i)
    {
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
        if(!c[i][j])s[i][j]=1;
    }
    go(i,2,2000)
    {
        go(j,1,i)s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        s[i][i+1]=s[i][i];
    }
}
int main()
{
    T=read();k=read();init();
    while(T--)
    {
        n=read(),m=read();
        if(m>n)m=n;
        printf("%lld
",s[n][m]);
    }
    return 0;
}