---
title: "越狱"
created: 2025-11-28
tags:
  - 算法
---

# 越狱

## 题目 [越狱](https://blog.csdn.net/w2259318982/article/details/130610280)

监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。

有 m 种宗教，每个犯人可能信仰其中一种。

如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。

求有多少种状态可能发生越狱。

输入格式

共一行，包含两个整数 m 和 n。

输出格式

可能越狱的状态数，对 100003 取余。

数据范围

$1≤m≤10^8, 1≤n≤10^{12}$

输入样例：

2 3 输出样例：

6 样例解释

所有可能的 6 种状态为：(000)(001)(011)(100)(110)(111)

## 思路分析

两种考虑01枚举状态 但是m种 没思路了

一看震惊了

![[image-b851f0f9.png]]

先找出所有不会发生越狱的情况 再把总情况一减

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 100003;

ll quickmi(ll a, ll k, ll p)

{

    ll res = 1 % p;

    while (k){

        if (k & 1)

            res = (res * a) % p;

        a = (a * a) % p;

        k >>= 1;

    }

    return res % p;

}

int main()

{

    ll n, m;

    cin >> m >> n;

    ll all = quickmi(m, n, mod) % mod;

    ll noty = quickmi(m - 1, n - 1, mod) % mod;

    cout << (all - (m * noty) % mod + mod) % mod;//有可能减出负数

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[序列的第k个数|序列的第k个数]] 🏠 [[00-刷题理模型]] ➡️ [[求逆元|求逆元]]