P5239回忆京都 题解

组合数递推公式递推出前1000*1000项组合数。

预处理一下前缀和。

\(O(1)\)回答。

代码：

#include<iostream>
#define int long long
using namespace std;
int C[1010][1010],s[1010][1010],q,n,m;
signed main()
{
	for(int i = 1;i <= 1000;i++) {
		C[i][i] = 1;
		C[i][0] = 1;
	}
	for(int i = 1;i <= 1000;i++) {
		for(int j = 1;j <= 1000;j++) {
			if(j > i) (C[j][i] = C[j - 1][i] + C[j - 1][i - 1]) %= 19260817;
		}
	}
	/*for(int i = 1;i <= 10;i++) {
		for(int j = 1;j <= 10;j++) {
			cout << C[i][j] << "\t";
		}
		cout << "\n";
	}*/
	for(int i = 1;i <= 1000;i++) {
		for(int j = 1;j <= 1000;j++) {
			s[i][j] = ((s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + C[i][j]) % 19260817 + 19260817) % 19260817;
		}
	}
	cin >> q;
	while(q--) {
		cin >> n >> m;
		swap(n,m);
		cout << s[n][m] << "\n";
	}
}