题目：P3197 [HNOI2008]越狱
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P3197
- 参考题解：https://www.luogu.com.cn/problem/solution/P3197
- 标签：
OI、数学、容斥
题解
思路
- 第一点：排列组合的问题，根据题意可以推导出来 s o l v e = m n − m ∗ ( m − 1 ) n − 1 solve = m^n−m∗(m−1)^{n−1} solve=mn−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 solve = binpow(m, n) - (m * binpow(m - 1, n - 1)) % mod + mod;printf("%lld", solve % 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;
}
