洛谷 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)

---

题解

这题还是很坑的，我一开始正着想，一直在推各种奇怪的式子，结果WA了好几次，最后迫不得已去看题解，结果发现这题要倒着想。。。
越狱情况数=总情况数-不越狱情况数
总情况数=$m^n$
然后，不越狱只要满足没有相邻的两个相同就可以，也就是每一个都和上一个不同。
不越狱情况数=$m*{(m-1)}^{n-1}$
越狱情况数=$m^n-m*{(m-1)}^{n-1}$
快速幂即可。
提醒大家一句，这题取模超级坑。。
code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=100003;
ll m,n;
ll ksm(ll a,ll b,ll p){ll ans=1;a%=p;while(b){if(b&1){ans=(ans*a)%p;}a=(a*a)%p;b>>=1;}return ans;
}
int main(){scanf("%lld %lld",&m,&n);ll ans=ksm(m,n,p)-m*ksm(m-1,n-1,p);while(ans<0){ans+=p*100;}printf("%lld",ans%p);return 0;
}

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

---