先算总状态数 m^n，再减去所有相邻房间宗教都不同的安全状态数 m·(m-1)^(n-1)。
OJ: luogu
题目 ID: P3197
难度:普及/提高-
标签:数学容斥快速幂思维
日期: 2026-06-20 06:52
题意
有 n 个房间，每个房间里的人可以信 m 种宗教中的一种。
如果存在某一对相邻房间宗教相同，就可能发生越狱。
要求统计“可能发生越狱”的状态数，对 100003 取模。
注意这题的输入顺序是：
- 先给宗教数
m - 再给房间数
n
思路
先看一个可以直接验证想法的小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int m, n;
int choose_color[20];
i64 ans = 0;
void dfs(int pos) {
if (pos == n + 1) {
for (int i = 1; i < n; i++) {
if (choose_color[i] == choose_color[i + 1]) {
ans++;
return;
}
}
return;
}
for (int c = 1; c <= m; c++) {
choose_color[pos] = c;
dfs(pos + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
dfs(1);
cout << ans % 100003 << '\n';
return 0;
}暴力版直接枚举每个房间的宗教，然后检查是否存在相邻相同。
它只能跑很小的数据，但非常适合拿来对拍。
正难则反
直接数“会越狱”的状态不太方便。
更自然的做法是：
- 总状态数
- 减去
- 完全不会越狱的安全状态数
于是答案就是：
总状态数 - 安全状态数
总状态数
每个房间都有 m 种选择，一共 n 个房间，所以：
total = m^n
安全状态数
如果完全不会越狱，说明每一对相邻房间的宗教都必须不同。
那么：
- 第一个房间有
m种选法 - 后面每个房间都不能和前一个相同，所以各有
m - 1种选法
所以安全状态数是：
safe = m * (m - 1)^(n - 1)
最终答案
因此：
ans = m^n - m * (m - 1)^(n - 1)
因为 n 和 m 都很大，幂次必须用快速幂算。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 MOD = 100003;
i64 quick_pow(i64 base, i64 exp) {
i64 ans = 1 % MOD;
base %= MOD;
while (exp > 0) {
if (exp & 1) {
ans = ans * base % MOD;
}
base = base * base % MOD;
exp >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 m, n;
cin >> m >> n;
i64 total = quick_pow(m, n);
i64 safe = m % MOD * quick_pow(m - 1, n - 1) % MOD;
i64 ans = (total - safe) % MOD;
if (ans < 0) {
ans += MOD;
}
cout << ans << '\n';
return 0;
}复杂度
主要是两次快速幂：
- 时间复杂度
- 空间复杂度
总结
这题是最典型的补集计数：
- 先算总方案
- 再算“不出事”的方案
- 用总数减掉安全数
真正的计算量只剩快速幂。