http://www.lydsy.com/JudgeOnline/problem.php?id=1008
刚开始看不会做啊，以为是dp，但是数据太大！！！所以一定有log的算法或者O1的算法，，，，还是不会。。
看了题解，，太巧妙了！就是反过来想。。所有情况-不会越狱的情况=答案。。。。所有情况很好求，因为每个人都可以是任意种宗教，根据乘法原理，所有情况=m*m*m*m*...*m=m^n；而不会越狱的情况也很好求，因为约束只是临边的人不能是同种宗教，所以我们只要假设临边的人有m-1种选择，而这个临边的临边也只有m-1种选择，所以不会越狱的情况=m*(m-1)*(m-1)*(m-1)*...*(m-1)=m*(m-1)^(n-1)。
因为数据大，用快速幂，复杂度为logn。
这里要注意负数处理，因为m^n>m*(m-1)^(n-1)，即a>b，所以(a-b)%c=(((a%c)+c)-(b%c))%c
#include <cstdio>
using namespace std;
typedef unsigned long long ull;
ull fastpow(ull a, ull b, int c) {
ull ret=1;
while(b) {
if(b&1) ret=(ret*a)%c;
a=(a*a)%c;
b>>=1;
}
return ret;
} int main() {
ull n, m;
scanf("%llu%llu", &m, &n);
printf("%llu\n", (fastpow(m, n, 100003)+100003-((ull)(m%100003)*fastpow(m-1, n-1, 100003))%100003)%100003);
return 0;
}
Description
*有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
Input
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
Output
可能越狱的状态数，模100003取余
Sample Input
2 3
Sample Output
6
HINT
6种状态为(000)(001)(011)(100)(110)(111)