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)
题解：我们先来考虑不会发生越狱的情况，第一个房间的人可以选择m种宗教中的任何一种，而后面的房间只能选择和前一个房间不同的宗教，所以能选择m-1种(如下图)。而总状态数（m^n）减去不会越狱的状态数就是会发生越狱的状态数。所以答案应该是m^n-m*(m-1)^(n-1)。由于减的时候会出现负数，所以要先加mod再%mod。
这里需要用到快速幂，然而我发现我的递归版的快速幂好像跑不出来OTZ，于是我想起学长曾经讲过的二进制快速幂，就到神犇的博客里学习了一下，还挺好懂的233（好吧，是我智障了OTZ）
代码如下：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const long long p=100003; long long ksm(long long a,long long k) { long long ans=1; for(;k;k>>=1,a=(a%p*a%p)%p) if(k&1) ans=(ans%p*a%p)%p; return ans%p; } int main() { long long n,m,ans; scanf("%lld%lld",&m,&n); printf("%lld",(ksm(m,n)%p-m%p*ksm(m-1,n-1)%p+p)%p); return 0; } /* 192072 101294871092 */