开始补ZR的任务清单/kel
题目描述
监狱有连续编号为 $1 \dots N$ 的 $N$ 个房间,每个房间关押一个犯人,有 $M$ 种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。
输入格式
输入两个整数 $M,N$
输出格式
可能越狱的状态数,对 $100003$ 取模
Inputs and Outputs examples
Inputs’ e.g. #1
1 | 2 3 |
Outputs’ e.g. #1
1 | 6 |
分析
这题我记得dls讲的时候是拿来签到的/cy
正难则反,我们考虑用总状态数减去不合法状态数即为答案.
显然总状态数为Tewelvefold way
里面的Problem LLA
,也就是$m^n$
考虑不合法状态数,即每两个相邻犯人的宗教都不同的方案数.
首先假设$1$号牢房的犯人信仰宗教$A$,这时$A$可以在$[1,m]$里面取值.为了和$1$号牢房犯人的宗教避开,$2$号牢房的犯人信仰的宗教$B$只能有$m-1$种取值.与之类似,为了和$2$号牢房犯人的宗教避开,$3$号牢房的犯人信仰的宗教$C$也只能有$m-1$种取值.
那么依次类推下去,显然可以得到答案:
$$Ans = m^n - m \times (m - 1) ^ {n-1}$$
快速幂即可,注意取模问题
代码
1 | /* Headers */ |