当前位置:首页 > 数学 > 快速幂 > 正文
SSOJ2898越狱[HNOI2008]
34+

题目大意:n个相邻的房间,m种宗教的犯人,同一种总结不相邻有多少种方案?

题目描述

原题来自:HNOI 2008

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

输入

输入两个整数 mn

输出

可能越狱的状态数,对 100003 取余。

提示

样例输入

2 3

样例输出

6

样例说明

所有可能的 6 种状态为:{0,0,0},{0,0,1},{0,1,1},{1,0,0},{1,1,0},{1,1,1}

对于全部数据,1m108,1n1012

解题思路

一个一个房间选宗教、填宗教,每个房间填1~m,分步用乘法原理,一共有$m^n$种方案。如果要合法,那么下一个房间不能跟前一个宗教相同,第一个可以选m种,其他只能选m-1种,共$m*(m-1)^{(n-1)}$种方案,相减即不合法方案数。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2898越狱[HNOI2008]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter