首页 > 代码库 > P3197 [HNOI2008]越狱
P3197 [HNOI2008]越狱
P3197 [HNOI2008]越狱
题目描述
监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
输入输出格式
输入格式：
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
输出格式：
可能越狱的状态数，模100003取余
输入输出样例
输入样例#1：
2 3
输出样例#1：
6
说明
6种状态为(000)(001)(011)(100)(110)(111)
分析
r如果没有限制，方案数就是m^n；然后有限制的话，第一个人取m个，那么他后边的人全都只能(m-1)个，方案数就是m*(m-1)^(n-1)，
答案就是：总方案数(m^n)-不冲突方案数( m*(m-1)^(n-1) )
代码
1 #include<cstdio> 2 #define mod 100003 3 long long m,n; 4 long long Pow(long long n,long long m) 5 { 6 if (m==0) return 1; 7 long long a = (Pow(n,m/2))%mod; 8 if (m&1) return ((a*a)%mod*n)%mod; 9 else return (a*a)%mod;10 }11 int main()12 {13 scanf("%lld%lld",&m,&n);14 printf("%lld",(Pow(m,n)-((m*Pow(m-1,n-1))%mod)+mod)%mod);15 return 0;16 }
P3197 [HNOI2008]越狱
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。