题意：监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
题解：设f[i]=有M种宗教i个房间时不发生越狱的方案数，显然f[1]=M，f[i]=f[i-1]*(M-1)。最后答案就是N^M-f[N]
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; #define ll long long const ll P=100003; ll N,M; ll QuickPow(ll a,ll b){ a%=P,b%=P-1; ll t=(b&1?a:1); while(b>>=1){ a=a*a%P; if(b&1) t=a*t%P; } return t; } int main(){ cin >> M >> N; cout << (QuickPow(M,N)-M*QuickPow(M-1,N-1)%P+P)%P << endl; return 0; }
原文：http://www.cnblogs.com/WDZRMPCBIT/p/6443505.html
