监狱有连续编号为 1…N的 N 个房间，每个房间关押一个犯人，有 M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
输入格式：
输入两个整数 M,N
输出格式：
可能越狱的状态数，模 100003 取余
众所周知，这种求有多少种状态的题都可以从反面想，也就是用所有状态减去所有不可行的状态。
这道题也就可以用这种方法，所有状态是N^M
而不可行的状态：
第一个人可能有M种宗教，如果不发生越狱，第二个人必须与第一个人不同，有M-1种。
第三个人不能和第二个人相同，但是可以和第一个人相同，所以也是M-1，
以此类推，一共有M*(M-1)^(N-1)种不会发生越狱的情况。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #define MAXN 100010 #define in(a) a=read() #define REP(i,k,n) for(int i=k;i<=n;i++) using namespace std; inline long long read(){ long long x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } long long n,m,mod; long long ksm(long long a,long long b){ long long ans=1; while(b){ if(b%2==1) ans=((ans%mod)*(a%mod))%mod; a=(a*a)%mod; b/=2; } return ans%mod; } int main(){ mod=100003; in(m),in(n); long long p=(ksm(m,n)%mod-m*ksm(m-1,n-1)%mod)%mod; if(p<0) p=(p+mod)%mod; cout<<p; return 0; }
转载于:https://www.cnblogs.com/jason2003/p/10470948.html
相关资源：JAVA上百实例源码以及开源项目