题解 P3197 [HNOI2008]越狱

题目描述

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

输入输出格式

输入格式:

输入两个整数 $ M,N $

输出格式:

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

输入输出样例

输入样例#1:

2 3

输出样例#1:

6

说明

6种状态为(000)(001)(011)(100)(110)(111)
$ 1 \le M \le 10^8 $
$ 1 \le N \le 10^{12} $

题解

考虑用总方案数减去不可能越狱的方案数
每个房间有m种可能 有n个房间 可以得到总方案数=$m^{n}$
然后就是不可能越狱的方案 如果两个房间的的宗教相同 就可能越狱
也就是要求相邻的两个房间宗教不同 那么第一个房间有 m 种可能
下一个房间只要与前一个房间不同就可以了 有 m-1 种可能
所以不越狱的方案总数等于 $ m(m-1)^{n-1} $
然后答案就等于 $ m^n-m*(m-1)^{n-1} $ 即为最后答案,用快速幂运算即可

Code:

发表评论