1008: [HNOI2008]越狱
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3140 Solved: 1317
[Submit][Status]
Description
*有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱
Input
输入两个整数M,N.1<=M<=10^8,1<=N<=10^12
Output
可能越狱的状态数,模100003取余
Sample Input
Sample Output
HINT
6种状态为(000)(001)(011)(100)(110)(111)
Source
分析:高中数学题……可能越狱=总-不可能越狱
一共n个位置,每个位置m个可能,所以总=m^n
第一个位置有m个可能;第二个位置要和第一个位置不同,故m-1个可能;第三个位置要和第二个位置不同,故m-1个可能……;不可能越狱=m*(m-1)^(n-1)
综上所述,ans=m^n-m*(m-1)^(n-1),然后算的时候每个地方mod一下就行了。注意到n很大,所以快速幂搞一下……
(这恐怕是bzoj最水的一题了,不过那些拼空间的大牛真是丧心病狂!16kB怎么办到的!)
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int p=;
long long power(long long a,long long b)
{
long long ans=;
while(b>)
{
if(b%==) ans=(ans*a)%p;
a=(a*a)%p;
b/=;
}
return ans;
}
int main()
{
long long n,m;
scanf("%lld%lld",&m,&n);
long long ans=(power(m,n)-(m*power(m-,n-))%p)%p;
if(ans<) ans+=p;
printf("%lld",ans);
return ;
}
【BZOJ1008】【HNOI2008】越狱(数学排列组合题)的更多相关文章
-
BZOJ 1008 [HNOI2008]越狱 (简单排列组合 + 快速幂)
1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 10503 Solved: 4558[Submit][Status ...
-
[BZOJ1008] [HNOI2008] 越狱 (数学)
Description *有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种.如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱 In ...
-
【BZOJ1008】越狱(排列组合计数,容斥原理)
题意: 思路: #include<cstdio> #include<cstdlib> #include<iostream> #include<algorith ...
-
bzoj1008: [HNOI2008]越狱 数学公式+快速幂
bzoj1008: [HNOI2008]越狱 O(log N)---------------------------------------------------------------- ...
-
BZOJ1008: [HNOI2008]越狱-快速幂+取模
1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 8689 Solved: 3748 Description *有 ...
-
4535 ACM 礼尚往来 数学排列组合
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4535 题意:每个礼物都不相同的组合个数 数学规律: 将每个女友排序为1···n,对应的女友送男友的礼物排序 ...
-
bzoj1008 [HNOI2008]越狱
1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5099 Solved: 2207 Description *有 ...
-
bzoj 1008: [HNOI2008]越狱 数学
1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MB[Submit][Status][Discuss] Description *有连 ...
-
[Bzoj1008][HNOI2008]越狱(组合计数)
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1008 组合计数的简单题,可能越狱的方案数等于总方案数-不可能越狱的方案数,则: 总方案数 ...
随机推荐
-
(四)G1 garbage collector
g1专为大内存,多内核机型设计.可以兼顾高吞吐量和低暂停时间. g1将堆分为多个相同大小内存块,并发的标记线程,使得g1掌握了各个内存块的活对象数量, 内存回收阶段,g1根据用户指定的暂停时间,选择部 ...
-
转 UML类图几种关系的总结
UML类图几种关系的总结 在UML类图中,常见的有以下几种关系: 泛化(Generalization), 实现(Realization),关联(Association),聚合(Aggregati ...
-
消息通信库ZeroMQ 4.0.4安装指南
一.ZeroMQ介绍 ZeroMQ是一个开源的消息队列系统,按照官方的定义,它是一个消息通信库,帮助开发者设计分布式和并行的应用程序. 首先,我们需要明白,ZeroMQ不是传统的消息队列系统(比如Ac ...
-
JAVAscript——菜单下拉列表练习(阻止事件冒泡)
下拉列表框,鼠标点击文本框,出现下拉,鼠标(离开的时候或者点击网页其他位置时)下拉列表消失.鼠标放到下拉列表的某一项上变背景色,点击下拉列表的某一项将该项的值显示在文本框内,然后下拉列表消失. < ...
-
tomcatserver乱码问题,tomcat与数据库之间的编码统一转换
在tomcat文件夹的conf文件夹下,改动server.xml文件,在以下截图中的位置加上URIEncoding="UTF-8"则表示tomcat编码转换为utf-8风格, 一般 ...
-
归纳篇(一)CSS的position定位和float浮动
近期会更新一系列博客,对基础知识再度做个巩固和梳理. 一.position定位 (一):position的属性 1.absolute:生成绝对定位的元素,相对于最近一级定位不是static的父元素来进 ...
-
可扩展标记语言XML
XML简述 XML用于描述数据,是当前处理结构化文档信息的有力工具.与操作系统编程语言的开发平台无关,可以实现不同系统之间的数据交互. 结构 <?xml version="1.0&qu ...
-
RAID及热备盘详解
RAID,为Redundant Arrays of Independent Disks的简称,中文为廉价冗余磁盘阵列. 一.出现的原因(RAID的优点): 它的用途主要是面向服务器,但现在的个人电脑由 ...
-
MP和OMP算法
转载:有点无耻哈,全部复制别人的.写的不错 作者:scucj 文章链接:MP算法和OMP算法及其思想 主要介绍MP(Matching Pursuits)算法和OMP(Orthogonal Matchi ...
-
(object) array
<?php $current_language = (object)array ( 'name' => '火星文', 'timezone' => 'Asia/Tokyo', 'aut ...