洛谷P3197 越狱

题目大意：

监狱有 n 个房间，每个房间关押一个犯人，有 m 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对100,003 取模。

对于 100% 的数据，保证1≤m≤10^8，1≤n≤10^12。

 学啥用啥！！！

要求有多少种状态可能发生越狱，我们可以求所有的安排牢房的状态 ，也就是全集。

 然后再算出所有的不会越狱的状态，也就是集合A。

用全集减去集合A，得到补集，这就是答案。

全集如何求？   

由乘法原理可知，每个牢房都可以安排m种宗教，也就是有m种选择，一共有n个牢房，那么全集就是：

接下来我们要求，所有不会越狱的状况，集合A。

也就是要使得每个相邻的房间宗教不同。

第一个房间的选择有m种，第二个房间的选择只要满足不和前面的房间相同即可，m-1种

第三个房间只要满足与第二个房间不同，也就是m-1种。

这样下来，每个房间都与自己前一个房间的宗教不同，从而使得每个相邻的房间宗教不同。

答案就是  

所以最终答案就是        mod （ 100003 ）

用快速幂即可

（千万记住先输入m再输入n，我被这个卡了好久！！！！）

然后别忘了特判   

 快速幂之和可能会小于0，再加上100003即可

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
const long long MOD = 100003;
typedef long long ll;
ll qpow(ll m, ll n) {ll s = 1;while (n) {if (n & 1)s = s * m % MOD;m = m * m % MOD;n >>= 1;}return s;
}
ll n, m,ans,cns,bns;int main() {cin >> m >> n;ans = qpow(m, n);bns = (m * qpow(m - 1, n - 1))%MOD;cns = (ans - bns)%MOD;if (cns < 0)cns += MOD;cout << cns;
}