简单数学题

首先有一个众所周知的组合数递推式：$C^i_j=C^{i-1}_j+C^i_{j-1}$。然后就可以预处理组合数了。

但是当 $i,j$ 足够大时，这会轻松地爆 long long。所以我们考虑转换问题：问 $k$ 是否可以整除 $C^i_j$，就是求 $(C^i_j \mod k)$ 是否为零，所以只需要边算边模 $k$ 就行了。

查询时遍历显然超时，所以可以二维前缀和一下。

#include <cstdio>
#include <algorithm>
using namespace std;

int c[2005][2005],s[2005][2005];

int main(){
	int t,k;
	scanf("%d%d",&t,&k);
	c[0][0]=1;
	for(int i=1;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++){
			s[i][j]=(s[i-1][j]+s[i][j-1]-s[i-1][j-1])+(j<=i&&!c[i][j]);
		}
	}
	while(t--){
		int n,m;
		scanf("%d%d",&n,&m);
		printf("%d\n",s[n][m]);
	}
	
    return 0;
}