[HNOI2008]越狱

Description

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

Solution

正难则反，考虑容斥解题

总方案数为\(m^n\)，不发生冲突的方案数为\(m(m-1)^{n-1}\)(除第一个人有m种宗教选择，其他人都只有m-1种)。

则答案为\(m^n-m(m-1)^{n-1}\)，可以用快速幂求解。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=100003;
ll n,m;
ll quickpow(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1) ans=(ans*x)%p;
        x=(x*x)%p;y>>=1;
    }return (ans+p)%p;
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    scanf("%lld%lld",&m,&n);
    printf("%d",(quickpow(m,n)+p-m*quickpow(m-1,n-1)%p)%p);
    return 0;
} 

[HNOI2008]越狱

原文：https://www.cnblogs.com/NLDQY/p/10703339.html