智子 的博客

智子 的博客

面对我们的骨灰,高尚的人们将洒出热泪。

题解 P3197 【[HNOI2008]越狱】

posted on 2020-02-10 15:49:58 | under 题解 |

思路

这道题可以从反面去考虑,即:先计算出不可能发生越狱的状态总数,并用它减去总状态数即为这道题要求的答案。

首先,在不失一般性的情况下,不妨设第一个房间里的犯人的宗教信仰为 $p$ ,则第二个房间里的烦人的宗教信仰不能为 $p$ ,因此第二个房间里的犯人的宗教信仰共有 $(m - 1)$ 种可能性。同理,第三个房间里的犯人的宗教信仰也共有 $(m - 1)$ 种可能性……故第二个到第 $n$ 个房间里的烦人的宗教信仰共有 $(n - 1)^{(m - 1)}$ 种可能性。而第一个房间里的犯人的信仰有 $n$ 种可能,故不可能发生越狱的状态总数为 $$n×(n - 1)^{(m - 1)}$$

那么,总状态数是多少呢?容易求的总状态数为 $n^m$ ,所以题目所求为 $$n^m-n×(n - 1)^{(m - 1)}$$

这道题还有一个要注意的地方: $m$ 最大为 $10^8$ ,因此要用快速幂来计算

AC代码:

#include<iostream>
using namespace std;

const long long MOD = 100003;

long long power(long long b, long long p) {
    if(p == 0) {
        return 1;
    }
    long long ans = power(b, p / 2);
    ans = ans * ans % MOD;
    if(p % 2 == 1) {
        ans = ans * b % MOD;
    }
    return ans;
}

int main() {
    long long m, n;

    cin >> m >> n;
    long long ans = ((power(m, n) - m * power(m - 1, n - 1)) % MOD + MOD) % MOD;
    cout << ans << endl;

    return 0;
}