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";
}
}