[HNOI2008]越狱 (组合数学)
2024-09-30 05:52:59
题目描述
监狱有连续编号为 1…N 的 N 个房间,每个房间关押一个犯人,有 M 种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。
输入输出格式
输入格式:
输入两个整数 \(M,N\)
输出格式:
可能越狱的状态数,模 100003取余
输入输出样例
输入样例#1:
2 3
输出样例#1:
6
说明
6种状态为(000)(001)(011)(100)(110)(111)
1≤M≤108
1≤N≤1012
Solution
这道题运用了正难反易的思想.
直接处理出合法的情况即可.
然后想一想: 第一个有 n 种情况,然后的话 第二个就有 n-1 种情况.
再依次类推,会发现,后面都是 n-1 种情况.
所以 ans 即为: $$mn-n*(n-1){m-1}.$$
套一个快速幂模板即可. 需要注意的是 ans 为负数的情况.
代码
#include<iostream> #include<cstdio>
using namespace std;
long long n,m,p;
long long quick_pow(long long s,long long ks)
{ if(ks==1)return s%p; long long k=s; ks--; while(ks>0)
{ if(ks%2==1)k=(k*s)%p;
ks/=2;
s=(s*s)%p;
} return k%p;
}
int main()
{
cin>>n>>m;
p=100003;
cout<<(quick_pow(n,m)%p-n*quick_pow(n-1,m-1)%p+p)%p;
//需要处理负数的时候,加上一个 p再 模一个 p 即可
return 0;
}
最新文章
- thinkphp 模板里a标签 href 带参数的 使用U函数方法
- [转]asp.net的ajax以及json
- linux更新系统之后,删除多余的开机启动项
- RDD操作
- thinking in java知识小记(一)
- asp.net MVC 验证注解
- JavaScript语言基础知识11
- 更换包管理工具npm为yarn
- 关于新建Eclipse新建一个WEB项目后创建一个jsp文件头部报错问题?
- css的各种动画
- windows远程登录报错 CredSSP不支持Oracle
- 阻塞队列(BlockingQueue)
- traceroute命令初探
- Inviting Friends(hdu3244 &;&; zoj3187)完全背包+二分
- BeautifulSoup 使用select方法详解(通过标签名,类名, id,组合,属性查找)
- GitLab项目迁移到Gerrit
- Python 3 与 Javascript escape 传输确保数据正确方法和中文乱码解决方案
- Opencv——摄像头设置
- web.xml的contextConfigLocation作用及自动加载applicationContext.xml
- 五、vue nextTick
热门文章
- JMeter3.2入门使用教程
- X11/Xlib.h: No such file or directory
- ubuntu16.0 安装 openstack
- 100行代码让您学会JavaScript原生的Proxy设计模式
- leecode 旋转数组
- Entity Framework插入数据报错:Validation failed for one or more entities
- Android(java)学习笔记143:Android中View动画之 XML实现 和 代码实现
- 新数据的GT列表
- windows下pycharm使用Anaconda安装包环境
- LeetCode 买卖股票的最佳时机