【BZOJ1008】【HNOI2008】越狱(数学排列组合题)

时间:2022-03-06 00:58:57

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

2 3

Sample Output

6

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】越狱(数学排列组合题)的更多相关文章

  1. BZOJ 1008 &lbrack;HNOI2008&rsqb;越狱 &lpar;简单排列组合 &plus; 快速幂&rpar;

    1008: [HNOI2008]越狱 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 10503  Solved: 4558[Submit][Status ...

  2. &lbrack;BZOJ1008&rsqb; &lbrack;HNOI2008&rsqb; 越狱 &lpar;数学&rpar;

    Description *有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种.如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱 In ...

  3. 【BZOJ1008】越狱(排列组合计数,容斥原理)

    题意: 思路: #include<cstdio> #include<cstdlib> #include<iostream> #include<algorith ...

  4. bzoj1008&colon; &lbrack;HNOI2008&rsqb;越狱 数学公式&plus;快速幂

    bzoj1008: [HNOI2008]越狱      O(log N)---------------------------------------------------------------- ...

  5. BZOJ1008&colon; &lbrack;HNOI2008&rsqb;越狱-快速幂&plus;取模

    1008: [HNOI2008]越狱 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 8689  Solved: 3748 Description *有 ...

  6. 4535 ACM 礼尚往来 数学排列组合

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4535 题意:每个礼物都不相同的组合个数 数学规律: 将每个女友排序为1···n,对应的女友送男友的礼物排序 ...

  7. bzoj1008 &lbrack;HNOI2008&rsqb;越狱

    1008: [HNOI2008]越狱 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 5099  Solved: 2207 Description *有 ...

  8. bzoj 1008&colon; &lbrack;HNOI2008&rsqb;越狱 数学

    1008: [HNOI2008]越狱 Time Limit: 1 Sec  Memory Limit: 162 MB[Submit][Status][Discuss] Description *有连 ...

  9. &lbrack;Bzoj1008&rsqb;&lbrack;HNOI2008&rsqb;越狱&lpar;组合计数&rpar;

    题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1008 组合计数的简单题,可能越狱的方案数等于总方案数-不可能越狱的方案数,则: 总方案数 ...

随机推荐

  1. &lpar;四&rpar;G1 garbage collector

    g1专为大内存,多内核机型设计.可以兼顾高吞吐量和低暂停时间. g1将堆分为多个相同大小内存块,并发的标记线程,使得g1掌握了各个内存块的活对象数量, 内存回收阶段,g1根据用户指定的暂停时间,选择部 ...

  2. 转 UML类图几种关系的总结

    UML类图几种关系的总结   在UML类图中,常见的有以下几种关系: 泛化(Generalization),  实现(Realization),关联(Association),聚合(Aggregati ...

  3. 消息通信库ZeroMQ 4&period;0&period;4安装指南

    一.ZeroMQ介绍 ZeroMQ是一个开源的消息队列系统,按照官方的定义,它是一个消息通信库,帮助开发者设计分布式和并行的应用程序. 首先,我们需要明白,ZeroMQ不是传统的消息队列系统(比如Ac ...

  4. JAVAscript——菜单下拉列表练习&lpar;阻止事件冒泡&rpar;

    下拉列表框,鼠标点击文本框,出现下拉,鼠标(离开的时候或者点击网页其他位置时)下拉列表消失.鼠标放到下拉列表的某一项上变背景色,点击下拉列表的某一项将该项的值显示在文本框内,然后下拉列表消失. &lt ...

  5. tomcatserver乱码问题&comma;tomcat与数据库之间的编码统一转换

    在tomcat文件夹的conf文件夹下,改动server.xml文件,在以下截图中的位置加上URIEncoding="UTF-8"则表示tomcat编码转换为utf-8风格, 一般 ...

  6. 归纳篇(一)CSS的position定位和float浮动

    近期会更新一系列博客,对基础知识再度做个巩固和梳理. 一.position定位 (一):position的属性 1.absolute:生成绝对定位的元素,相对于最近一级定位不是static的父元素来进 ...

  7. 可扩展标记语言XML

    XML简述 XML用于描述数据,是当前处理结构化文档信息的有力工具.与操作系统编程语言的开发平台无关,可以实现不同系统之间的数据交互. 结构 <?xml version="1.0&qu ...

  8. RAID及热备盘详解

    RAID,为Redundant Arrays of Independent Disks的简称,中文为廉价冗余磁盘阵列. 一.出现的原因(RAID的优点): 它的用途主要是面向服务器,但现在的个人电脑由 ...

  9. MP和OMP算法

    转载:有点无耻哈,全部复制别人的.写的不错 作者:scucj 文章链接:MP算法和OMP算法及其思想 主要介绍MP(Matching Pursuits)算法和OMP(Orthogonal Matchi ...

  10. &lpar;object&rpar; array

    <?php $current_language = (object)array ( 'name' => '火星文', 'timezone' => 'Asia/Tokyo', 'aut ...