【第9题】容斥原理：P3197 [HNOI2008]越狱

小码匠

发布于 2023-08-31 13:59:46

2260

发布于 2023-08-31 13:59:46

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

题目：P3197 [HNOI2008]越狱

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

https://www.luogu.com.cn/problem/P3197
- 参考题解：https://www.luogu.com.cn/problem/solution/P3197
标签：数学、容斥

题解

思路

第一点：排列组合的问题，根据题意可以推导出来

ans = m^n−m∗(m−1)^{n−1}

第二点：快速幂（快速幂是我的盲区知识点，所以第一版代码TLE）

代码（没使用快速幂，TLE）

#include <bits/stdc++.h>
using namespace std;
const long long mod = 100003;

void best_coder() {
    long long n, m, t, a;
    scanf("%lld%lld", &m, &n);
    t = m;
    a = m - 1;
    for (long long i = 1; i < n; ++i) {
        m %= mod;
        m *= t;
        m %= mod;
    }
    for (long long i = 1; i < n; ++i) {
        t %= mod;
        t *= a;
        t %= mod;
    }
    printf("%lld", (m - t + mod) % 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;
}

AC代码

#include <bits/stdc++.h>
using namespace std;
const long long mod = 100003;

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = res * a;
            res %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return res % mod;
}

void best_coder() {
    long long n, m;
    scanf("%lld%lld", &m, &n);
    long long ans = binpow(m, n) - (m * binpow(m - 1, n - 1)) % mod + mod;
    printf("%lld", 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;
}

END

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

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

cin