「HNOI2008」越狱 - 计数原理

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

链接

BZOJ 1008

题解

考虑计算「不会越狱的方案数」,用「方案总数」减去「不会越狱的方案数」即可。

方案总数:一共 N 个位置,每个位置有 M 种选择,总方案数为 M ^ N

不会越狱的方案数:第一个位置有 M 种选择,之后每个位置都不能与上一个位置相同,即有 M - 1 种选择,方案数为 M * (M - 1) ^ {N - 1}

所以答案为 M ^ N - M * (M - 1) ^ {N - 1}

代码

#include <cstdio>

const long long MAXN = 1e12;
const long long MAXM = 1e8;
const long long MOD = 100003;

inline long long pow(const long long x, const long long n) {
    long long ans = 1;
    for (long long num = x % MOD, k = n; k; num = num * num % MOD, k >>= 1) if (k & 1) ans = ans * num % MOD;
    // for (int i = 0; i < n; i++) ans = ans * x % MOD;
    return ans;
}

int main() {
    long long m, n;
    scanf("%lld %lld", &m, &n);

    long long ans = pow(m, n) - m * pow(m - 1, n - 1);
    printf("%lld\n", (ans % MOD + MOD) % MOD);

    return 0;
}