【题目来源】
洛谷：P3197 [HNOI2008] 越狱 - 洛谷
【题目描述】
监狱有 \(n\) 个房间，每个房间关押一个犯人，有 \(m\) 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
答案对 \(100,003\) 取模。
【输入】
输入只有一行两个整数，分别代表宗教数 \(m\) 和房间数 \(n\)。
【输出】
输出一行一个整数代表答案。
【输入样例】
2 3
【输出样例】
6
【解题思路】
【算法标签】
《洛谷 P3197 越狱》 #数学# #组合数学# #容斥原理# #各省省选# #2008# #湖南# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 100003;
int m, n;// 快速幂：计算 a^b mod p
int qmi(int a, int b, int p)
{int mul = 1;while (b){if (b & 1) mul = mul * a % p; // 如果b的二进制最后一位是1a = a * a % p; // 平方b >>= 1; // 右移一位}return mul;
}signed main()
{cin >> m >> n;// 计算m^n mod modint a = qmi(m, n, mod);// 计算m * (m-1)^(n-1) mod modint b = (m * qmi(m - 1, n - 1, mod)) % mod;// 计算(a - b + mod) mod mod，避免负数int ans = (a - b + mod) % mod;cout << ans << endl;return 0;
}
【运行结果】
2 3
6