洛谷P5160 WD与循环

开发者柯欣技术 2022年11月21日

0 收藏 648 点赞 3,826 浏览 1114 个字

我们看这段代码

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是质数，所以这里使用了Lucas定理

哦对了还要用乘法逆元的线性求法

下面代码

#include <bits/stdc++.h>
#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;
}