测试地址：☞
【题目描述】
原题来自：HNOI 2008
监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。有 m 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。
【输入】
输入两个整数 m 和 n。
【输出】
可能越狱的状态数，对 100003 取余。
【输入样例】
2 3【输出样例】
6【提示】
样例说明
所有可能的 6 种状态为：{0,0,0},{0,0,1},{0,1,1},{1,0,0},{1,1,0},{1,1,1}。
数据范围与提示：对于全部数据，1 ≤ m ≤ 10^8,1 ≤ n ≤ 10^12 。
【思路】
有 n 个房间， m 种宗教，就有 m^n 种可能
有两种思路：
1. 分别判断相邻 2、3、4……个房间犯人信仰的宗教相同，但是这个实现难度较大，复杂度高，故舍弃。
2. 出现相邻总数目 = 所有可能 - 任意两个都不相邻的情况，即 sum = m^n - m*(m-1)^(n-1)
例如：有 3 种宗教，4 间房间，即 m = 3，n = 4；
—— —— —— —— （ 每个横线表示一个空格）
3 2 2 2 （数字表示在前面房间放入宗教后 在该房间可以放入的宗教总数）
其中 m^n: 表示所有情况 3^4
所以 m*(m-1)^(n-1) 就表示任意两个都不相邻的总情况数
故 sum = 3^4 - 3 * 2^3 = 57；
【AC代码】
#include<iostream> using namespace std; long long quick_power(long long x, long long y){ int ans=1; while(y){ if(y & 1) ans = (ans*x)%100003; x = (x*x)%100003; y >>= 1; } return ans; } int main(){ long long m, n, x, y, sum; cin >> m >> n; x = quick_power(m, n); y = quick_power(m-1, n-1); sum = (x - (m%100003)*(y%100003)%100003) % 100003; if(sum<0){ sum += 100003; } cout << sum; return 0; }