很好地体现了正难则反的思想。
总共的状态是m^n，不发生越狱则是要与前一个的宗教不同，那么这一个监狱的选择是m-1种。
总共不越狱的状态是m*（m-1）^（n-1）。
越狱的就是m^n-m*（m-1）^（n-1）
#include<bits/stdc++.h> #define LL long long #define mod 100003 using namespace std; LL read() { LL f=1,x=0;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } LL quick(LL a,LL x) { LL ans=1; while(x) { if(x&1)ans=ans*a%mod; a=a*a%mod; x>>=1; } return ans%mod; } int main() { LL m=read(),n=read(); printf("%lld\n",((quick(m,n)-quick(m-1,n-1)*m%mod)%mod+mod)%mod); } /* */
[HNOI2008]越狱（bzoj1008）（组合数学+正难则反）
原文：https://www.cnblogs.com/yyys-/p/11436662.html
