P2822 [NOIP2016 提高组] 组合数问题 讲解

· · 题解

题目
先在这放两个组合数公式：

C_n^m=\frac{n!}{m!(n-m)!} C_n^m=C^m_{n-1}+C_{n-1}^{m-1}

第一个公式大家都知道，第二个公式其实就是 dp。对于每个物品，要么选（C_{n-1}^{m-1}），要么不选（C_{n-1}^m）。
那么，运用第二个式子，提前计算出所有 n,m\le 2\times 10^3 的 C_n^m。
那么组合数都有了，但 O(Tnm) 的时间复杂度仍然会被卡，我们得想办法让每次询问都变成 O(1)，就得使用前缀和优化，即：

sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+[(C_{i,j}\bmod k=0)\lor(C_{i,j}\ne0)]

总体复杂度：O(nm+T)，可以通过。
代码： 

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define reg register
#define INF 2147483647
using namespace std;
inl int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
inl void write(int x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
}
#define N 2005
int t,k,f[N][N],sum[N][N],n,m;
inl void init(){
    f[1][1]=1;
    for(reg int i=2;i<=N-4;++i)
        for(reg int j=1;j<=i;++j)
            f[i][j]=(f[i-1][j]+f[i-1][j-1])%k;
    for(reg int i=1;i<=N-4;++i)
        for(reg int j=1;j<=N-4;++j)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(!f[i][j]&&j<=i);
    return;
}
inl void solve(){
    n=read();
    m=read();
    write(sum[n+1][m+1]);
    puts("");
}
signed main(){
    t=read();
    k=read();
    init();
    while(t--) solve();
    return 0;
}