[HNOI2008],[bzoj1008] 越狱（dp+组合数学）

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1008

Description

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

Input

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

Output

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

Sample Input

　　2 3

Sample Output

HINT

　　6种状态为(000)(001)(011)(100)(110)(111)

本题运用正难则反的思想，令dp[i]表示前i个监狱有多少种不发生越狱的状态，易得：dp[i]=dp[i-1]*(m-1) ，dp[1]=m; 即每个人只要保证与前面的人宗教不同。
所以可得出答案为 ans=m^n-m*(m-1)^(n-1);
n太大怎么办？快速幂咯。

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int mod=;

 long long n,m,ans;

 long long po(long long a,long long b) {

     long long sum=,base=a;

     while (b) {

         if (b%) sum=(sum*base+mod) % mod;

         base=(base*base+mod) % mod;

         b>>=;

     }

     sum%=mod;

     return sum;

 }

 int main() {

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

     ans=(m*(po(m,n-)-po(m-,n-))+mod) % mod;

     while (ans<) ans+=mod;

     printf("%lld\n",ans);

     return ;

 }

巴特西