【BZOJ】1008: [HNOI2008]越狱(组合数学)
2024-09-16 14:00:30
题目
题目描述
监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱
输入输出格式
输入格式:
输入两个整数M,N.1<=M<=108,1<=N<=1012
输出格式:
可能越狱的状态数,模100003取余
输入输出样例
输入样例#1: 复制
2 3
输出样例#1: 复制
6
说明
6种状态为(000)(001)(011)(100)(110)(111)
分析
对于这道题目本来是想写dp瞎搞的,然而看到数据范围就怂了。从洛谷上看了看标签,是组合数学,于是开始推式子,推了很久也并没有用。
其实处理有多少可能越狱是很困难的,但是处理有多少可能是不越狱是很简单的,然后减一减就可以了。
总共:m^(n) 不越狱:m* ((m-1)^(n-1))。
P.s.多模几次又不花钱,一定要多模(Wa了好几发,55555)
代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=100003;
ll poww(ll a,ll b)
{
ll base=a,ans=1;
while(b!=0)
{
if(b&1) ans=(ans*base)%mod;
base=(base*base)%mod;
b=b>>1;
}
return ans;
}
int main()
{
ll n,m;
scanf("%lld%lld",&m,&n);
printf("%lld",(poww(m,n)-((poww(m-1,n-1)*m)%mod)+mod)%mod);
return 0;
}
最新文章
- 从零开始编写自己的C#框架(3)——开发规范(转)
- 激活windows10 LTSB 2016
- 莫队算法 2038: [2009国家集训队]小Z的袜子(hose)
- WebSocket 是什么原理?为什么可以实现持久连接?
- Web service project中导入的库JAX-RS(Java EE 6.0新产品)
- PHP常用魔术方法(__call魔术方法:)
- iOS多线程系列(3)
- UVa 116 Unidirectional TSP (DP)
- if最简单的用法
- 6.python内置函数
- 使用dom4j技术对xml文档进行增删改练习(一)
- Docker &; ASP.NET Core (5):Docker Compose
- 记录使用nodejs时,未正确使用import导致的错误
- tomcat下的Cookie特殊符号问题
- CSS Media Query
- Union and Intersection of two sorted lists 并集和交集
- Confluence 6 快捷键
- Linux 实用指令之查看端口开启情况
- Python05 函数
- Mac OS X 下android环境搭建