C++14(g++5.4) 解法, 执行用时: 47ms, 内存消耗: 34660K, 提交时间: 2020-03-14 09:45:40

#include <bits/stdc++.h>
using namespace std;
int c[3000][3000];
int summ[3000][3000];

int main()
{
	int t,k; cin >> t >> k;
	int a,b;
	int w = 0;
	for(int i = 0; i <= 2100; i++)
	{
		w = 0;
		c[i][0] = c[i][i] = 1;
		for(int j = 1; j < i; j++)
		{
			c[i][j] = (c[i-1][j]+c[i-1][j-1])%k;
			if(c[i][j] == 0) w++;
			summ[i][j] = summ[i-1][j]+w;
		}
		summ[i][i] = summ[i][i-1];
	}
	while(t--)
	{
		cin >> a >> b;
		cout<<summ[a][min(a,b)]<<endl;
	}
	return 0;
}

C 解法, 执行用时: 43ms, 内存消耗: 29872K, 提交时间: 2023-01-17 11:37:20

#include <stdio.h>
const int M=2005;
int main(){
    int t,k,n,m,C[M][M],sum[M][M];
	scanf("%d%d",&t,&k);
	for(int i=1;i<=2000;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%k; 
	}
	for(int i=1; i<=2000; i++)
		for(int j=1;j<=2000;j++){
			int x = 0;
			if(i>=j) x=(C[i][j]==0);
			sum[i][j]=sum[i-1][j]+sum[i][j-1]+x-sum[i-1][j-1];
		}
		while(t--){
			scanf("%d%d",&n,&m);
			printf("%d\n",sum[n][m]);
		}	
		return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 76ms, 内存消耗: 30040K, 提交时间: 2019-11-09 11:49:59

#include <bits/stdc++.h>
using namespace std;
int c[2001][2001],ans[2001][2001],n,m,t,k;
int main() {
	cin>>t>>k;
	c[0][0]=1;
	for(int i=1; i<=2000; i++) {
		c[i][0]=1;
		for(int j=1; j<=2000; j++) {
			if(i>=j) {
				c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
				if(c[i][j]==0)ans[i][j]=1;
			}
			ans[i][j]+=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
		}
	}
	while(t--){
		cin>>n>>m;
		cout<<ans[n][m]<<endl;
	}
	return 0;
}