欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1008
题意概括
*有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
题解
水题一道。
我们考虑发生越狱的是总数-不发生越狱的。
总数很好算：就是mn
但是不发生的同样也很好算。
第一个位置，有m中选择，后面每一个位置都要和前面一个不一样，那么有m-1种选择。
所以是m*(m-1)n-1
答案就是mn-m(m-1)n-1，快速幂就可以了，取模，模数为100003
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const LL mod=100003;
LL Pow(LL x,LL y){
if (y==0)
return 1LL;
LL xx=Pow(x,y/2);
xx=xx*xx%mod;
if (y&1LL)
xx=xx*x%mod;
return xx;
}
LL x,y;
int main(){
scanf("%lld%lld",&x,&y);
printf("%lld",(Pow(x%mod,y)-x*Pow((x-1)%mod,y-1)%mod+mod*3)%mod);
return 0;
}