AcWing 1290. 越狱

题目传送门

一、解题思路

本题可以采用容斥原理补集的思想。

考虑 \(n\) 个犯人，\(m\)种宗教，如何安排不会导致犯罪。

第一个位置可以有 \(m\) 个选择，则与第一个相邻的第二个位置就只有 \(m?1\) 中选择。

考虑第 \(i\) 个位置，则为了不和他左侧的 \(i?1\) 位置发生冲突，一共有 \(m?1\) 种选择。

因此不会导致犯罪的方案是: \(m?(m?1)^{n?1}\)
则会导致犯罪的方案是：\(m^n?m?(m?1)^{n?1}\)

计算一个数字的\(n\)次方，还要求取模，自然就需要使用快速幂~

注意
一般在求快速幂时，底都是正整数，但，幂指数要能大于\(INT_MAX\)!\(n\)的数据范围太\(BT\)了，居然达到了\(1e12\)_,开$LL$,在\(qmi\)实现时，注意\(k\)的类型开\(LL\)!

注意减法取模可能会变成负数，那么我们要把他转化正数
\((a - b + mod) \% mod\) 即可

二、实现代码

#include 
using namespace std;

//快速幂
typedef long long LL;
const int mod = 100003;
int qmi(int a, LL k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int main() {
    int m;
    LL n;
    scanf("%d%lld", &m, &n);
    printf("%d\n", (qmi(m, n) - (LL)m * qmi(m - 1, n - 1) % mod + mod) % mod);

    return 0;
}