题目

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

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

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

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

输入格式
共一行，包含两个整数 m 和 n。

输出格式
可能越狱的状态数，对 100003 取余。

数据范围
1≤m≤108,
1≤n≤1012
输入样例：
2 3
输出样例：
6
样例解释
所有可能的 6 种状态为：(000)(001)(011)(100)(110)(111)。

思路

• 正着不行那就反向思考,即有多少种不会发生越狱的情况,对于第一个人，有m种，之后呢因为不能和前面相同，所以只有m-1种，总方案数减去不能越狱的方案数就是答案了

代码

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int mod = 100003;int qmi(int a, LL k)
{int res = 1;while (k){if (k & 1) res = (LL)res * a % mod;a = (LL)a * a % mod;k >>= 1;}return res;
}int main()
{int m;LL n;cin >> m >> n;cout << (qmi(m, n) - (LL)m * qmi(m - 1, n - 1) % mod + mod) % mod << endl;return 0;
}