bzoj1008越狱(组合数学+快速幂)

我不是女神ヾ 2021-09-15 13:34 314阅读 0赞

Problem 1008. – \[HNOI2008\]越狱

## 1008: \[HNOI2008\]越狱 ##

Time Limit: 1 Sec   Memory Limit: 162 MB  
Submit: 11735   Solved: 5087  
\[ Submit\]\[ Status\]\[ Discuss\]

## 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 ##

\[ Submit\]\[ Status\]\[ Discuss\]   
HOME  
Back

一句话题解：先考虑的所有的状态m^n,然后考虑不越狱的状态m\*(m-1)^(n-1),两者相减

为什么写这种简单题的题解，因为没有1A，又死在%上了

an = (power(m,n,mod)-m%mod\*power(m-1,n-1,mod)%mod+mod)%mod;  
第一遍没有加mod，m^n%mod以后小于后者

#include <bits/stdc++.h>
    using namespace std;
    
    const int mod = 100003;
    int power(long long  a,long long b,int p)
    {
        int ans = 1%p;
        for(; b; b>>=1)
        {
            if(b&1)
                ans = (long long)ans*a%p;
            a = (long long)a*a%p;
        }
        return ans;
    }
    
    long long n,m;
    int main()
    {
        cin>>m>>n;
        long long an;
        an = (power(m,n,mod)-m%mod*power(m-1,n-1,mod)%mod+mod)%mod;
        cout<<an<<endl;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，314人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDOJ 1008-Elevator【数学】

<table style=""> <tbody> <tr> <td style=""> <h1>Elevator</h1> </td> </tr

桃扇骨/ 2022年08月19日 01:42/ 0 赞/ 137 阅读

相关【lightoj1008】数学找规律

C - C 使用long long Time Limit:500MS Memory Limit:32768KB 64bit IO Format:%lld & %llu S

绝地灬酷狼/ 2022年07月17日 00:27/ 0 赞/ 180 阅读

相关 ACdream 1007 a + b (数学+快速幂)

题目链接： [ACdream 1007 ][ACdream 1007] 题目： ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEas

左手的ㄟ右手/ 2022年06月13日 01:18/ 0 赞/ 164 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 296 阅读

相关快速幂和矩阵快速幂

前言新年第一篇技术类的文章，应该算是算法方面的文章的。看标题：快速幂和矩阵快速幂，好像挺高大上。其实并不是很难，快速幂就是快速求一个数的幂（一个数的 n 次方）。

╰+攻爆jí腚メ/ 2022年06月01日 08:10/ 0 赞/ 285 阅读

相关 Applese 涂颜色（组合数学 + 快速幂 + 费马小定理 + 大数运算）

链接：[https://ac.nowcoder.com/acm/contest/330/E][https_ac.nowcoder.com_acm_contest_330_E]

客官°小女子只卖身不卖艺/ 2022年04月23日 08:30/ 0 赞/ 182 阅读

相关组合数学 (一): 快速幂运算

快速幂快速幂运算 C语言实现应用快速幂运算普通幂运算复杂度为 O(N) 快速幂运算复杂度为 O(lgN) 举个例子: 如

谁践踏了优雅/ 2022年03月21日 08:58/ 0 赞/ 272 阅读

相关 BZOJ1005:[HNOI2008]明明的烦恼(组合数学,Prufer)

Description 自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求

àì夳堔傛蜴生んèń/ 2021年12月22日 05:43/ 0 赞/ 166 阅读

相关 [bzoj4589]Hard Nim(FWT快速沃尔什变化+快速幂)

题面：[https://www.lydsy.com/JudgeOnline/problem.php?id=4589][https_www.lydsy.com_JudgeOnli

左手的ㄟ右手/ 2021年12月03日 07:53/ 0 赞/ 185 阅读

相关 bzoj1008越狱(组合数学+快速幂)

Problem 1008. – \[HNOI2008\]越狱 1008: \[HNOI2008\]越狱 Time Limit: 1 Sec Memory Limit

我不是女神ヾ/ 2021年09月15日 13:34/ 0 赞/ 315 阅读