1008: [HNOI2008]越狱

題目鏈接:http://www.lydsy.com/JudgeOnline/problem.php?id=1008

題意

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

解法

組合數學
總的情況數sum=mⁿ
總的不越獄的情況數目sub=m*(m-1)^n-1
最後的結果res=sum-sub

typedef long long LL;
const LL mod=100003;
LL pows(LL x,LL y) {
    LL res=1;
    while(y) {
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y=y>>1;
    }
    return res;
}
void solve() {
    LL n,m;
    while(cin>>m>>n) {
        LL sum=pows(m,n);
        LL sub=(pows((m-1)%mod,n-1)*m)%mod;
        LL res=(sum+mod-sub)%mod;
        cout<<res<<endl;
    }
}