写这篇博客是为了警示自己别总是局限于标签.

luogu典型的标签坑人系列.

题面:P3197 [HNOI2008]越狱

这道题输入只有两个数,让人不禁怀疑这到底是道什么题.按照DP标签来搜题的我陷入了沉思.一看数据范围顿时就怂了,这是什么神题,于是默默打开了题解.然后我才意识到:
$$
\textbf{这就是一道数学题,别怀疑自己了}
$$
由于直接算越狱的情况数并不方便,所以我们正难则反,用总的方案数减去不会越狱的方案数.总的方案数是多少呢?每个犯人有$M$种选择,一共有$N$个犯人,那么总方案数应该是$M^N$.然后如果不会越狱就代表相邻犯人信仰不同.我们按顺序考虑.对于左数第一个犯人,他有$M$种选择,而对于下一个犯人,显然只剩下了$M-1$种选择.那么对于下一个犯人是不是只剩下了$M-2$种选择呢?不是! 因为我们只要求相邻的不同,所以第三个犯人仍然可以选择第一个犯人的选择.那么还是$M-1$种.所以答案就是:
$$
M^N-M\times (M-1)^{N-1} (mod\ \ 100003)
$$
谨以此博客祭奠我浪费在瞎想上的时间