思路

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

首先，在不失一般性的情况下，不妨设第一个房间里的犯人的宗教信仰为$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;
}

版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 许可协议。转载请注明出处！
本文链接：https://keepthethink.github.io/archives/4021524966/