<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

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

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

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

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

输入格式

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

输出格式

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

数据范围

$1 \\le m \\le 10^8$,
$1 \\le n \\le 10^{12}$

输入样例：

2 3

输出样例：

6

样例解释

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

思路

$n$个犯人，$m$种宗教。
不越狱的数量：$m\times (m-1)^{n-1}$ （后面的都不能与前面的相同）
一共的数量：$m^n$
越狱的数量：$m^n-m\times (m-1)^{n-1}$

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int MOD = 100003;
LL m,n;
LL power (LL a,LL b,LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int main () {
    cin >> m >> n;
    cout << ((power (m,n,MOD) - m * power (m - 1,n - 1,MOD)) % MOD + MOD) % MOD << endl;
    return 0;
}