「一本通 6.1 练习 3」越狱

题目描述

监狱有连续编号为 $1$ 到 $n$ 的 $n$ 个房间，每间关押一名犯人，共有 $m$ 种宗教。若存在相邻两间房间的犯人信仰同一宗教，就可能发生越狱。求可能发生越狱的状态数对 $100003$ 取余的结果。

输入一行两个整数 $m$ 和 $n$ （ $1 \le m \le 10^8$ ， $1 \le n \le 10^{12}$ ），输出可能越狱的状态数 mod $100003$ 。样例输入 2 3，样例输出 6。

思路

正难则反：全部状态数为 $m^n$ ；「不越狱」要求所有相邻房间信仰都不同，第 $1$ 间有 $m$ 种选法，之后每间避开左邻恒有 $m-1$ 种，共 $m(m-1)^{n-1}$ 个。答案 $= m^n - m(m-1)^{n-1} \bmod 100003$ ， $n$ 高达 $10^{12}$ ，两个幂用快速幂求，减法为负时补回模数。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 22:18
# update_at: 2026-09-30 22:23

import sys

MOD = 100003  # 题面要求的模数


def solve() -> None:
    """总状态数减掉「相邻房间宗教都不同」的状态数，剩下的就是至少有一对相邻同教的状态数。"""
    m, n = map(int, sys.stdin.buffer.read().split())

    all_states = pow(m, n, MOD)  # 每个房间从 m 种宗教里任选
    safe_states = m * pow(m - 1, n - 1, MOD)  # 第 1 间任选，之后每间避开左邻的宗教

    print((all_states - safe_states) % MOD)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:19
 * update_at: 2026-10-06 01:19
 */

#include <cstdio>

typedef long long ll;

const ll MOD = 100003; // 题面要求的模数

ll m, n; // m 种宗教，n 个房间

// 计算 a^b mod MOD，快速幂
ll qpow(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%lld %lld", &m, &n);

    // 全部状态数 m^n 减去不越狱数 m*(m-1)^(n-1)
    // n=1 时没有相邻对，m-1 的 0 次方为 1，公式给出 0，天然正确
    ll all_states = qpow(m, n);
    ll safe_states = m % MOD * qpow(m - 1, n - 1) % MOD;

    // 减法可能出负数，补回模数
    ll ans = ((all_states - safe_states) % MOD + MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}

「一本通 6.1 练习 3」越狱

目录

题目描述

思路

参考代码