【第36题】重要：阅读神犇的代码是种享受之 [NOIP2011 提高组] 计算系数

小码匠

发布于 2023-08-31 14:36:46

2150

发布于 2023-08-31 14:36:46

文章被收录于专栏：小码匠和老码农

碎碎念

2分钟根据二次项定理推出了公式，然后花1个小时写代码…………………………o(╥﹏╥)o
作业：学习逆元

题目：[NOIP2011 提高组] 计算系数

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P1313
- 参考题解：https://www.luogu.com.cn/problem/solution/P1313
标签：OI、 NOIP、数学
难度：普及/提高-

30分

思路

利用组合数的定义式,但是因为有取余, 所以要用逆元，而由于本人并不了解逆元，所以精度应该是被卡爆后华丽丽的WA了. 推导公式如下。

C_n^m

\frac {n! mod 10007} {m!(n-m)! mod 10007}

n!×[m!(n−m)!]^{−1}

mod

10007

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

const int mod = 10007;

void best_coder() {
    int a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;
    int t = min(n, m);
    long long ans = 1;
    for (int i = 0; i < t; ++i) {
        ans *= k - i;
        ans /= i + 1;
        ans %= mod;
    }
    for (int i = 0; i < n; ++i) {
        ans *= a;
        ans %= mod;
    }
    for (int i = 0; i < m; ++i) {
        ans *= b;
        ans %= mod;
    }
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

30分

思路

扫了遍题解，猛然想起组合式有个递推公式可以算组合数，然而由于递归耗费了大量时间，所以不开快速幂是铁定过不了的，当然k最大为1000，所以索引数组下标开小后就RE了，并且最后答案还少了次取模，因此在出题人良心大发下拿了30分

C_n^m=C_{n−1}^m+C_{n−1}^{m−1}

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

const int mod = 10007;
int c[1000][1000];

int number (int k, int t) {
    if (t == 0 || k == t) {
        c[k][t] = 1;
        return c[k][t];
    }
    if (t == 1) {
        c[k][t] = k;
        return c[k][t];
    }
    c[k][t] = number(k - 1, t) % mod + number(k - 1, t - 1) % mod;
    return c[k][t];
}

void best_coder() {
    int a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;
    int t = min(n, m);
    long long ans;
    ans = number(k, t);
    for (int i = 0; i < n; ++i) {
        ans *= a;
        ans %= mod;
    }
    for (int i = 0; i < m; ++i) {
        ans *= b;
        ans %= mod;
    }
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

100分

思路

较上一版代码更正了错误，这里有个点需要注意，a和b的初始值可能大于mod所以要先取余（不过有没有影响本人也没测试过，反正取余了铁定没问题就是了）

代码

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

const int mod = 10007;
int c[1010][1010];


int quick_pow(int x, int y) {
    int ans = 1, t = x;
    while (y) {
        t %= mod;
        if (y % 2 == 1) {
            ans *= t % mod;
            ans %= mod;
        }
        t = (t * t) % mod;
        y >>= 1;
    }
    return ans % mod;
}

int number(int k, int t) {
    if (t == 0 || k == t) {
        c[k][t] = 1;
        return c[k][t];
    }
    if (t == 1) {
        c[k][t] = k;
        return c[k][t];
    }
    if (c[k][t] != 0) {
        return c[k][t];
    }
    c[k][t] = (number(k - 1, t) + number(k - 1, t - 1)) % mod;
    return c[k][t];
}

void best_coder() {
    int a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;
    int t = min(n, m);
    long long ans = 1;
    c[1][0] = 1;
    c[1][1] = 1;
    a %= mod;
    b %= mod;
    ans *= quick_pow(a, n) % mod;
    ans *= quick_pow(b, m) % mod;
    ans *= number(k, t);
    cout << ans % mod;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

100分

思路

这是别的神犇的代码，在本蒟蒻心（非）平（常）气（抓）和（狂）的研究了这份代码后简单说下
- 这位神犇他是干脆将a和b直接揉到了系数的计算过程中，同时用了（大概可能应该）dp思想???用上述提到的公式推了系数出来

代码

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

const int mod = 10007;
int c[1010][1010];

void happy_coder() {
    long long a, b, k, n, m;
    cin >> a >> b >> k >> n >> m;
    c[1][1] = 1;
    for (int i = 2; i <= k + 1; i++) {
        for (int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j - 1] * b + c[i - 1][j] * a) % 10007;
        }
    }
    cout << c[k + 1][m + 1];
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    //best_coder();

    // 最优解
    happy_coder();

    // 返回
    return 0;
}

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-06-08，如有侵权请联系 cloudcommunity@tencent.com 删除

cin