洛谷 P3197 [HNOI2008]越狱 题解
2024-09-07 15:23:37
P3197 [HNOI2008]越狱
题目描述
监狱有连续编号为 \(1…N\) 的 \(N\) 个房间，每个房间关押一个犯人，有 \(M\) 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
输入格式
输入两个整数 \(M,N\)
输出格式
可能越狱的状态数，模 \(100003\) 取余
输入输出样例
输入 #1
2 3
输出 #1
6
说明/提示
6种状态为(000)(001)(011)(100)(110)(111)
\(1 \le M \le 10^8\)
\(1 \le N \le 10^{12}\)
【思路】
组合数学 + 快速幂
【题目大意】
n个房间里面都有犯人，他们信仰m种不同的宗教
求有至少一对信仰相同宗教的人挨在一起的情况
【核心思路】
正着求是很难求或者是没有办法求的
所以正难则反
没法直接求出来越狱的情况
那就求出总的情况和不越狱的情况
用总的情况减去不越狱的情况
就是题目要求我们求的越狱的情况
总的情况
每一个房间都有m中可能，一共有n个房间
所以可能性是m^n次方
总的情况就知道了
然后看不会越狱的情况
第一个房间可以有m中选择
第二个房间不能和第一个房间的宗教一样‘
所以只有m-1中可能
第三个也是和第二个一样
所以出现了一个m和n-1个m-1
那么不会越狱的情况就是m*(m-1)^(n-1)
知道了这两个
一做差就可以求出来会越狱的情况了
【小细节】
幂运算很大需要用快速幂
【完整代码】
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int mo = 100003;
int p(int a,int b)
{
int ans = 1;
while(b != 0)
{
if(b & 1 == 1)
{
ans *= a;
ans %= mo;
}
b /= 2;
a = ((a % mo) * (a % mo)) % mo;
}
return ans;
}
signed main()
{
int n,m;
cin >> m >> n;
cout << ((p(m,n) % mo - (m * p(m - 1,n - 1)))%mo + mo ) % mo;//先做减法，因为减法之后可能出现负数，但是这个负数的绝对值一定会小于m的 ，因为这是两个已经%过m的数，保证小于m所以做的差的绝对值也一定小于m，只需要将这个可能是服饰的数加上mo保证是正数之后再%一遍mo
return 0;
}
最新文章
- 《大型网站系统与Java中间件实践》读书笔记
- Android Gradle 多Module单独编译一个Module
- Scala 深入浅出实战经典 第63讲：Scala中隐式类代码实战详解
- iOS CoreData学习资料 和 问题
- [APAC]手动截取当前活动窗口,并且按规则命名(1/2)
- Emmet使用手册
- 使用Word 2013向cnblog发布博文
- 采用subversion管理iOS资源
- 一个误解: 单个服务器程序可承受最大连接数“理论”上是“65535”
- osip及eXosip的编译方法
- ES6__异步开发优化
- 服务网关基于RPC的用法
- 微信公众号开发C#系列-7、消息管理-接收事件推送
- Xamarin Forms Api请求开源框架Refit
- 2018年-2019年第二学期第三周C#学习个人总结
- CF 1013E Hills
- C++: 带参数回调函数和不带参数的回调函数；
- WEB前端面试2014阿里旺旺
- 用matlab绘制中国地图
- nodejs 数字字节转换操作