跳转至

算法笔记

BISHI69 [HNOI2008]越狱

w3903771/algorithm

BISHI69　[HNOI2008]越狱¶

简单通过率 42.59%python3样例通过牛客 AC

牛客原题　源码

讲解章节：组合数学

一句话

N 个房间各选 M 种宗教之一，求「存在相邻同宗教」的方案数 mod 100003。

解题思路¶

这题考什么¶

正难则反 + 乘法原理。

总方案数：每间房独立选，M^N；
不会越狱（任意相邻都不同）的方案：第 1 间任选 M 种，之后每间只要和前一间不同，各有 M-1 种 -> M * (M-1)^(N-1)；
答案 = M^N - M*(M-1)^(N-1)，再模 P = 100003。

验算样例：M=2, N=3 -> 2^3 - 21^2 = 8 - 2 = 6 ✓ N = 1 时：M - M(M-1)^0 = M - M = 0，符合直觉（只有一间房谈不上相邻）。

数据规模与复杂度¶

M <= 1e8，N <= 1e12。指数到 1e12，必须快速幂 —— 用内置 pow(a, b, P)， C 层实现，O(log N) 次模乘，一次询问微秒级。

坑在哪¶

不能用费马小定理把指数降到 N mod (P-1)：M 可能是 P = 100003 的倍数（M <= 1e8 完全够大），此时 M ≡ 0 (mod P)，费马小定理的前提 gcd(M,P)=1 不成立，降幂会算错。直接 pow(M % P, N, P) 就好，log(1e12) 才 40 层，没必要降；
相减可能得负数，最后统一 % P 转正（Python 的 % 自动给非负结果）；
M = 1 时 (M-1) = 0，pow(0, N-1, P) 在 N=1 时是 pow(0,0,P)=1，答案 1 - 1*1 = 0；N >= 2 时是 0，答案 1 - 0 = 1，都正确；
N 到 1e12 超过 int32。

参考实现¶

solutions/BISHI69.py
import sys

P = 100003

# 只有一行两个数，取前两个 token 即可
m, n = map(int, sys.stdin.buffer.read().split()[:2])
# 正难则反：先数「所有分配方案」，再扣掉「一次越狱机会都没有」的方案
total = pow(m % P, n, P)                       # M^N
safe = m % P * pow((m - 1) % P, n - 1, P) % P  # M*(M-1)^(N-1)：任意相邻都不同
# 相减可能为负，末尾统一取模；Python 的 % 直接给出 [0,P) 内的结果
sys.stdout.write(str((total - safe) % P) + "\n")