[问题 9] 宽容原则：P3197 [HNOI2008] 越狱
最编程
2024-03-26 10:28:48
...
题目：P3197 [HNOI2008]越狱
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P3197
- 参考题解：https://www.luogu.com.cn/problem/solution/P3197
- 标签：
数学、容斥
题解
思路
- 第一点：排列组合的问题，根据题意可以推导出来
- 第二点：快速幂（快速幂是我的盲区知识点，所以第一版代码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