首先我们来看一个有趣的东西

1 1 1 1 2 1 1 3 3 1

1 4 6 4 1

是不是很眼熟！！这就是一个杨辉三角

所以c(i,j)的值就是第i行第j列

预处理的时候膜?K就好了

那么问题来了，预处理好杨辉三角形，还有T组询问怎么办？？？

我们可以用一个叫做矩阵和的东西（就是下面的S数组）给个口诀吧，上加左 减左上 加自己

这样看预处理只需要2000*2000的时间而面对T次询问，每次询问只需要O（1）的时间就可以回答，是不是超级方便！！！

下面粘一波代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t,k,n,m;
int c[2005][2005],s[2005][2005];
void prepare();
int main(){
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    cin>>t>>k;
    prepare();
    while(t--){
        cin>>n>>m;
        if(m>n) m=n;
        cout<<s[n][m]<<endl;
    }    
    return 0;
} 
void prepare(){
    c[1][1]=1;
    for(int i=0;i<=2000;i++) c[i][0]=1;
    for(int i=2;i<=2000;i++){
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
        }
    }
    for(int i=2;i<=2000;i++){
        for(int j=1;j<=i;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            if(c[i][j]==0) s[i][j]+=1;
        }
        s[i][i+1]=s[i][i];
    }
}

#include <iostream>
using namespace std;
int C[2005][2005],f[2005][2005],t,n,m,k;
int main(){
	cin>>t>>k;
	for (int i=0;i<=2000;++i){ 
		C[i][0]=1;
		for (int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
	}
	for (int i=1;i<=2000;++i)
		for (int j=1;j<=2000;++j){
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1];//二维前缀和 
			if (j<=i) f[i][j]+=(C[i][j]==0);//判断C[i][j]是合法位置 
		}
	while (t--){
		cin>>n>>m;
		cout<<f[n][m]<<"\n";
	}
}
 

暴力枚举的时间复杂度是 $O(tn^2)$ 级别的，百分百超时。

这题本质上是求在杨辉三角中 $(1,1)$ 到 $(n,m)$ 中有多少个数是 $k$ 的倍数。因此我们可以预处理出杨辉三角数组 $c$，然后利用二维前缀和计算出 $f$ 数组，$f[i][j]$ 表示在 $c$ 数组中 $(1,1)$ 到 $(i,j)$ 有多少个数是 $k$ 的倍数。

预处理代码如下：

// 套用计算杨辉三角的板子并稍加修改
for(ll i=1;i<=M;i++){ // M=2000
    c[i][0]=1;
    for(ll j=1;j<=i;j++)
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%k; // 在计算c数组时就%k会更快一些
}
for(ll i=1;i<=M;i++)
    for(ll j=1;j<=M;j++) // 注意for的判断条件不能写成j<=i，因为j>i的部分也需要赋值
        if(j<=i)
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(!c[i][j]); // 套用二维前缀和公式，如果c[i][j]为0即c[i][j]可以被k整除，那么将f[i][j]在之前的基础上+1
        else
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]; // j>i的部分f[i][j]为前面的和

当我们预处理好 $f$ 数组后，每一次回答就变为 $O(1)$ 的了。这样总的算下来时间复杂度为 $O(t+M^2)$，可以通过。

以下是完整AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2005,M=2000;
ll t,k,c[N][N],f[N][N];
int main(){
    scanf("%lld%lld",&t,&k);
    for(ll i=0;i<=M;i++){ // 预处理
        c[i][0]=1;
        for(ll j=1;j<=i;j++)
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
    }
    for(ll i=1;i<=M;i++)
        for(ll j=1;j<=M;j++)
            if(j<=i)
                f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(!c[i][j]);
            else
                f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
    for(ll i=1,n,m;i<=t;i++){
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",f[n][m]);
    }
    return 0;
}