本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-01 22:02:02

题目
先在这放两个组合数公式：
$$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;
}