1008: [HNOI2008]越狱(计数问题)
2024-09-03 13:20:52
1008: [HNOI2008]越狱
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 11361 Solved: 4914
[Submit][Status][Discuss]
Description
监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果
相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱
Input
输入两个整数M,N.1<=M<=10^8,1<=N<=10^12
Output
可能越狱的状态数,模100003取余
Sample Input
2 3
Sample Output
6
HINT
6种状态为(000)(001)(011)(100)(110)(111)
分析
正着想不好想,反过来想,求不发生越狱的方案数,用总方案数减去即可。
总方案数$=m^n$,每个房间都有m中选择
不发生越狱的方案数$=m*(m-1)^{n-1}$,第一个房间有m中选择,因为第二个不能和第一个相同,所以有m-1个选择,第3,4...n个房间都是这样。
code
#include<cstdio>
#include<iostream> using namespace std;
typedef long long LL;
const LL mod = ; LL ksm(LL a,LL b) {
LL ret = ;
while (b) {
if (b & ) ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= ;
}
return ret % mod;
}
int main() {
LL m,n;
cin >> m >> n;
cout << ( (ksm(m,n) - m*ksm(m-,n-)%mod + mod) % mod); //-在m*ksm(..)需要mod
return ;
}
最新文章
- Java多线程同步 synchronized 关键字的使用
- 理解伪元素 :Before 和 :After
- hdu 1342(DFS)
- hdu 3695:Computer Virus on Planet Pandora(AC自动机,入门题)
- svn提交时强制添加注释
- 使用Ps制作透明ico
- Android Studio集成SVN报错:can&#39;t use subversion command line client : svn
- APP 上架苹果应用商城
- LED流水灯(二)
- 树形DP+树状数组 HDU 5877 Weak Pair
- hdu2112(HDU Today 简单最短路)
- DicomIoException: Requested 132 bytes past end of fixed length stream.
- 2818: Gcd
- Python之排序算法:快速排序与冒泡排序
- express学习(三)—— cookie和session
- [HTML]将错误alert出来[转]
- Liunx服务管理(Centos)
- Leetcode刷题第004天
- 面试汇总——说一下CSS盒模型
- [CF1030E]Vasya and Good Sequences
热门文章
- Stuts2的 ";struts.devMode"; 设置成true后,不起作用,仍需要重启tomcat
- Extjs4几个小知识点
- MVC框架的实现
- MSMQ学习笔记二——创建Message Queue队列
- April 19 2017 Week 16 Wednesday
- py常见模块
- 1.10 从表中随机返回n条记录
- 解决Jenkins的错误“The Server rejected the connection: None of the protocols were accepted”
- Oracle 日期加减运算
- 【CCPC-Wannafly Winter Camp Day3 (Div1) G】排列(水题)