我们看这段代码

int cnt = 0;for (int a_1 = 0; a_1 <= m; a_1++) {    for (int a_2 = 0; a_1 + a_2 <= m; a_2++) {    ...        for (int a_n = 0; a_1 + a_2 + ... + a_n <= m; a_n++) {            cnt = (cnt + 1) % 19491001;        }    }}printf("%d\n", cnt);

其实是可以改写为

int cnt = 0;for (int a_1 = 1; a_1 <= m + n; a_1++) {    for (int a_2 = 1; a_1 + a_2 <= m + n; a_2++) {    ...        for (int a_n = 1; a_1 + a_2 + ... + a_n <= m + n; a_n++) {            cnt = (cnt + 1) % 19491001;        }    }}printf("%d\n", cnt);

答案不变（就是把\(a_0, a_1, ... , a_n\)全部加了1，源代码里相应的\(m\)要增加\(n\)，因为n个循环变量，每个变量都增加了1，所需增加即为\(n \times 1 = n\)）

然后根据组合数学中组合数的定义，所求为C(m + n, n)

由于数特~别~大~，而且19491001是质数，所以这里使用了

哦对了还要用

下面代码

#include 
    
     #define int long long#pragma GCC optimize(3)#pragma GCC optimize("Ofast")using namespace std;const int maxn = 20000000;const int p = 19491001LL;int n, inv[maxn], m, js[maxn];int Lucas(int n, int m){    if(n < m)return 0LL;    if(n < p)return js[n] * inv[m] % p * inv[n - m] % p;    return Lucas(n % p, m % p) * Lucas(n / p, m / p) % p;}signed main(){    int t;    scanf("%lld", &t);    js[0] = 1LL;    for(register int i = 1LL; i <= p; i++)js[i] = js[i - 1] * i % p;    inv[1] = 1LL; inv[0] = 1LL;    for(register int i = 2LL; i <= p; i++)inv[i] = (p - p / i) * inv[p % i] % p;    for(register int i = 2LL; i <= p; i++)inv[i] = inv[i] * inv[i - 1] % p;    while(t--)    {        scanf("%lld%lld", &n, &m);        printf("%lld\n", Lucas(n + m, m));    }    return 0;}
    

三年OI一场空，不开long long见祖宗