首页 > 试题广场 >

[HNOI2008]越狱

[编程题][HNOI2008]越狱
  • 热度指数：601 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}监狱共有按顺序编号 1\sim N 的 N 个房间，每个房间关押一名犯人。已知存在 M 种宗教，每名犯人恰好信仰其中一种。

\hspace{15pt}若存在相邻房间 (i,i+1) 的两名犯人信仰相同宗教，则可能发生越狱。请计算，可能发生越狱 的分配方案数量，对 P=100\,003 取模。

输入描述:
\hspace{15pt}在一行上输入两个整数 M,N 满足 
\hspace{23pt}\circ\, 1\leqq M\leqq 10^8； 
\hspace{23pt}\circ\, 1\leqq N\leqq 10^{12}。


输出描述:
\hspace{15pt}输出一个整数，表示可能发生越狱的方案数量模 P 的值。
示例1

输入

2 3

输出

6
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-07-14 18:08:43
题目链接 [HNOI2008]越狱 题目描述 监狱有 个房间，按顺序编号 。共有 种宗教，每名犯人信仰其中一种。 如果存在相邻房间的两名犯人信仰相同宗教，就可能发生越狱。 请计算可能发生越狱的分配方案总数，结果对 取模。 输入: 一行输入两个整数 。 输出: 输出一个整数，表示可能发生越 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-08-29 09:58:18
题目链接 [HNOI2008]越狱 题目描述 监狱有 个房间，每个房间关押一名犯人，共有 种宗教。如果相邻房间的犯人信仰同一种宗教，则可能发生越狱。请求出可能发生越狱的方案总数，结果对 取模。 解题思路 直接计算“至少有一对相邻犯人信仰相同”的方案数比较复杂，需要考虑多种情况并应用容斥原理。一 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：2025年秋招-中国联...
难度：
0条回答 224浏览

热门推荐

相关试题

[HNOI2008]越狱

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号