【bzoj题解】1008 越狱

题目描述

监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

输入

输入两个整数M，N。1<=M<=10^8，1<=N<=10^12。

输出

可能越狱的状态数，模100003取余

样例输入

2 3

样例输出

6

题解

越狱状态数=总状态数-不越狱状态数=\(m^{n}-m\cdot\left(m-1\right)^{n-1}\)

快速幂+取模

 #include<cstdio>

 const int Mod=;

 int m;long long n;

 int pow(int base,long long exp){

     int ans=;

     while(exp){

         if(exp&) ans=1ll*ans*base%Mod;

         base=1ll*base*base%Mod;

         exp>>=;

     }

     return ans;

 }

 int main(){

     scanf("%d%lld",&m,&n);

     printf("%d",((pow(m,n)-1ll*m*pow(m-,n-))%Mod+Mod)%Mod);

     return ;

 }