BZOJ 1008: [HNOI2008]越狱-程序员宅基地

技术标签：快速幂 BZOJ

BZOJ 1008: [HNOI2008]越狱

题目

Time Limit: 1 Sec Memory Limit: 162 MB

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*（m-1）^(n-1)种，已知总方案数就是m^n,那么越狱的方案数也就可知了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib> 
#define mod 100003
#define ll long long
using namespace std;
ll m,n;
ll qpow(ll a,ll b)
{
    ll c=1,d=a%mod;
    while (b>0)
    {
        if (b&1) c=(c%mod*d%mod)%mod;
        b>>=1;
        d=(d%mod*d%mod)%mod;
    }
    return c;
}
int main()
{
    scanf("%lld%lld",&m,&n);
    long long ans=qpow(m,n);
    ans=ans-m*qpow(m-1,n-1)%mod;
    if (ans<0)  ans+=mod;
    printf("%lld",ans);
    return 0;
}

本文链接：https://blog.csdn.net/faojie/article/details/72059655

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

多重网络与计算机之间是感叹号,win10系统连接网络出现多重网络的设置教程-程序员宅基地

文章浏览阅读1.1k次。win10系统使用久了，好多网友反馈说win10系统连接网络出现多重网络的问题，非常不方便。有什么办法可以永久解决win10系统连接网络出现多重网络的问题，面对win10系统连接网络出现多重网络的图文步骤非常简单，只需要　　一、打开电脑win10系统的任务栏，然后看到一个“网络和共享中心”选项打开它，就看到了网络和interne的窗口上，在选择“更改适配器设置”这个选项。　二、我们点击打开了“..._电脑多重网路怎么设置

framework.jar文件push进去不起效_android 11 push framework方法-程序员宅基地

文章浏览阅读613次。Android源码编译结果中framework/arm目录和framework/arm64目录（如果有的话）中的boot.art和boot.oat两个文件替换掉系统相应的/system/framework/arm目录和/system/framework/arm64目录中的同名文件，也可以把framework.jar给push进/system/framework/中，然后把/system/fra..._android 11 push framework方法

编码规范(一)----JAVA注释规范_java 注释规范-程序员宅基地

文章浏览阅读3.4w次，点赞26次，收藏120次。一、前言好的代码规范是一个程序员的基本修炼，好的代码注释更能体现一个程序员的思维逻辑，虽然代码是用来给机器运行的，我们只要能写出能让编译器运行的代码就行了，但是如果没有好的编码规范，到项目后期，加入开发的人员逐渐增多时，每个人的编码风格都不一样，这就会让项目维护者很难维护，所以开始就要制定一些好的规范来让大家遵守，这样才能写出可维护，健壮的项目，这就是接下来要做的事情。第一节从要从代码_java 注释规范

Qt设置Widget窗口背景图片_qt的窗口背景图片更换-程序员宅基地

文章浏览阅读195次。1）声明重绘事件Qt中的重绘事件是Qt默认的函数，只需要对其自己编写定义，当窗口运行时，程序就会自动调用重绘事件，首先我们需要在头文件中声明重绘事件#include <QPaintEvent> //添加头文件... ... protected: void paintEvent(QPaintEvent *event); //重绘事件2）重绘事件定义在cpp文件中对重绘事件重新编写，比如这里我们想要让窗口背景设置成一张图片//添加绘画头文件#incl_qt的窗口背景图片更换

蛮力法解决01背包问题-程序员宅基地

文章浏览阅读1.6w次，点赞5次，收藏66次。蛮力法：设计算法求解背包问题，并编程实现。背包问题: 给定重量分别为,价值分别为的n件物品，和一个承重为W的背包。求这些物品中一个最有价值的子集，并能装到背包中。背包问题的蛮力解法是穷举这些物品的所有子集，找出能够装到背包中的所有子集，并在这些子集中找出价值最大的子集。实验：编写程序，实现背包问题的蛮力算法。并针对以下两个实例，求出能装到背包中的价值最大的子集。要求输出：最优可..._蛮力法解决01背包问题

Oracle PL-SQL 的使用_oracle数据库plsql使用-程序员宅基地

文章浏览阅读776次。使用PL-SQL1.关于PL-SQL（功能、特点及语法结构）2.数据类型（%type与%rowtype）3.PL-SQL控制语句4.异常处理5.函数============================================PL/SQL是过程语言PL与结构化查询语言SQL结合而成的编程语言。 PL/SQL是针对Oracle数据库的；它是过程语言 + 结构化查询语言的结合；过程语言PL：如变量声明，流程的控制，循环等；查询语言SQL：SQL语..._oracle数据库plsql使用

随便推点

python------给定一个句子(只包含字母和空格),将句子中的单词位置反转,单词用空格分割, 单词之间只有一个空格,前后没有空格。_给定一个句子(只包含字母和空格), 将句子中的单词位置反转,单词用空格分割, 单词-程序员宅基地

文章浏览阅读9k次，点赞5次，收藏23次。python之字符串练习2：将句子中的单词位置反转1）题目描述> 给定一个句子（只包含字母和空格），将句子中的单词位置反转，单词用空格分割, 单词之间只有一个空格，前后没有空格。比如：（1） “hello xiao mi”-> “mi xiao hello”输入描述:> 输入数据有多组，每组占一行，包含一个句子(句子长度小于1000个字符)输出描述:> 对于每个测试示例，要求输出句子中单词反转后形成的句子示例1:- 输入 hello xiao mi_给定一个句子(只包含字母和空格), 将句子中的单词位置反转,单词用空格分割, 单词