分析

• n个犯人，m中宗教信仰，问给每个人分配一个宗教信仰，使得存在相邻的人宗教信仰相同，有多少种方案数？

• 我们可以求一下一共有多少种分配方式，然后减去不符合题目要求的分配方案，就是结果。

• 一共的分配方案数，因为每个人都可以被分配m中宗教信仰中的一个，因此总方案数为：$m^n$。

• 不符合题目要求的方案数，即不存在相邻的人宗教信仰相同，则第一个人可以分配m中宗教信仰中的一个，后面的人均可以分配m-1中宗教信仰中的一个（只需要不和前一个相同即可），因此不符合题目要求的方案数为：$m \times (m - 1) ^ {n - 1}$。

• 因此分配方案数为：$m^n - m \times (m - 1) ^ {n - 1}$。

代码

#include <iostream>

using namespace std;

typedef long long LL;

const int mod = 100003;

int qmi(int a, LL k) {

    int res = 1 % mod;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int main() {

    LL n;  // n个人
    int m;  // m中宗教信仰
    cin >> m >> n;

    cout << (qmi(m, n) - (LL)m * qmi(m - 1, n - 1) % mod + mod) % mod << endl;

    return 0;
}