二位前缀和+排列组合 组合数问题

· · 个人记录

需要计算i,j不超过某个范围的所有组合数中有多少个k的倍数。首先看到n,m都是2e3，直接用阶乘算组合数，由于有阶乘，每次都是O(n)的复杂度，n,m2e3，意味着需要计算的组合数的总个数可能到4e6，直接T。

因此像这种需要多次使用组合数的情况，最好用递推计算组。计算不超过n的组合数，只需要O(n)的时间，之后每次查询都是O(1),和直接算一个组合数的时间相当！

至于这题问有哪些是k的倍数，可以在递推时膜k,后面检查时，如果是0，就是k的倍数。

看似就这样完了，但如果由于是多组输入，如果直接遍历所有组合数，还是会T。因此还可以先二位前缀和预处理一下，这样对于每个查询就都是O(1)的了。

这里的二维前缀和还有个问题，一般的前缀和公式就是pre(i,j)=pre(i-1,j)+pre(i,j-1)-pre(i-1,j-1)+a(i,j)，但问题是这里的i,j都是组合数的参数，可能会出现没有对应的pre(i-1,j).比如对于c(4,4)，计算pre(4,4)需要c(3,4)，但这个组合数是不存在的。推pre(4,4)实际上需要的是pre(3,3)和pre(4,3)，因此可以把pre(3,3)赋给pre(3，4)，这样就能沿用一般二位前缀和的形式。并且这里不需要加a(i,j)，而是看c(i,j)是否为0，如果为0总数就加一。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define ll long long 
#define db double
#define inf 0x3f3f3f3f
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define rep1(i,x,y) for(int i=(x);i>=(y);i--)
#define pll pair<int,int>
int rd(void)
{
    int x=0,f=1;char s;
    s=getchar();
    while(s>'9'||s<'0'){
        if(s=='-')f=-1;
        s=getchar(); 
    }
    while(s<='9'&&s>='0'){
        x=x*10+s-'0';
        s=getchar(); 
    }
    x*=f;
    return x;
}
int c[2010][2010],pre[2010][2010];
int main(){
    int t,k;
    cin>>t>>k;
    rep(i,0,2000){
        c[i][0]=c[i][i]=1;//这两个组合数可以直接初始化
        rep(j,1,i-1)c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;//膜k，一方面避免爆int，一方面直接记录是否是k的倍数
    }
    rep(i,1,2000){
        rep(j,1,i){
            pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];//正常二位前缀和的形式
            if(c[i][j]==0)pre[i][j]++;//如果c(i,j)是k的倍数，加一
        }
        pre[i][i+1]=pre[i][i];//维持二位前缀和的形式不变
    }
    rep(p,1,t){
        int n,m;
        cin>>n>>m;
        cout<<pre[n][min(m,n)]<<'\n';//每个询问O(1)查询
    }
}