bzoj1008: [HNOI2008]越狱 数学公式+快速幂

bzoj1008: [HNOI2008]越狱      O（log N）
-----------------------------------------------------------------------------------------------------------------------------------------
　　*有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
-----------------------------------------------------------------------------------------------------------------------------------------
　　输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
-----------------------------------------------------------------------------------------------------------------------------------------
　　可能越狱的状态数，模100003取余
-----------------------------------------------------------------------------------------------------------------------------------------
       Sample Input      2 3
       Sample Output   6
-----------------------------------------------------------------------------------------------------------------------------------------
HINT 6种状态为(000)(001)(011)(100)(110)(111)

考察到 N , M 数据范围极大，甚至 递推 或 1..M 或 1..N 的操作都不行。
考虑本题是否可以推导 O（1） 或 O（log N）数学公式
观察到每个房间中的囚犯可能信仰1..M中任意一个宗教，于是得到  总共会有 M^N 种状态
又发现如果正向推导十分困难，于是考虑 逆向思维 ，推导共有多少种状态不会越狱，
可以看到第一位囚犯可能信仰 M 种宗教，而后的每一种因前面有一位罪犯信仰某一宗教而受限制，
因此只有 M-1 种选择，故  不会越狱的状态数为 M*(M-1)^(N-1) 种
综上所述，可以看出本题的   可能越狱的状态数为 ( M^N - M*(M-1)^(N-1) ) % 100003
再使用快速幂对公式加速可以将 O（N）加速到 O（log N）

 #include<iostream>
 #include<cstdio>
 using namespace std;

 typedef long long ll;
 const ll mod=1e5+;
 ll n,m;

 ll mod_pow(ll n,ll m){ //快速幂
     ll ret=;
     while (m>){
         if (m&) (ret*=n)%=mod;
         (n*=n)%=mod;
         m>>=;
     }
     return ret;
 }

 int main(){
     scanf("%lld%lld",&m,&n);
     ll ans=mod_pow(m,n)-m*mod_pow(m-,n-)%mod; //公式
     ans%=mod;
     printf("%lld\n",(ans+mod)%mod); // 为防止ans为负数，对 ans+mod 再%mod，保证 ans 为正
     return ;
 }