洛谷P5160 WD与循环

我们看这段代码

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;

}

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

巴特西

洛谷P5160 WD与循环

最新文章

热门文章