越狱

题目 越狱

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

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

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

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

输入格式

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

输出格式

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

数据范围

输入样例：

2 3 输出样例：

6 样例解释

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

思路分析

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

一看震惊了

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

代码实现

#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个数 🏠 00-刷题理模型 ➡️ 求逆元