越狱hnoi2008

本文主要是介绍越狱hnoi2008，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述 Description
监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
输入描述 Input Description
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
输出描述 Output Description
可能越狱的状态数，模100003取余
样例输入 Sample Input
2 3
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
6种状态为(000)(001)(011)(100)(110)(111)

思路:这个题虽是省选，但并不难，经过数学分析可以发现总的方案为m^n,不会发生越狱的方案为m*(m-1)^(n-1)。
所以答案就是m^n-m*(m-1)^(n-1);
在减法取模的时候要注意一下会不会减出负数。。。

#include<iostream>
using namespace std;
long long n,m,temp,ans,ans2,a,b;
int main()
{cin>>m>>n;ans=1;b=n;a=m;a=a%100003;while (b>0){if (b%2==1)ans=(ans*a)%100003;b/=2;a=(a*a)%100003;}ans2=1;b=n-1;a=m-1;a=a%100003;while (b>0){if (b%2==1)ans2=(ans2*a)%100003;b/=2;a=(a*a)%100003;}ans2=(ans2*(m%100003))%100003;ans=ans+100003-ans2;if (ans>100003)ans-=100003; cout<<ans;
}

这篇关于越狱hnoi2008的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---