目录

题目-越狱

在这里插入图片描述

问题分析

直接计算发生越狱情况比较难以计算, 可以逆向思维, 计算总的情况, 减去不发生越狱的情况, 剩余的就是越狱的情况
第一个犯人有 m m m种选择, 第二个 m − 1 m - 1 m−1, 第三个 m − 1 m - 1 m−1, 第四个 m − 1 m - 1 m−1, …
因此总的不发生越狱的情况数量 m × ( m − 1 ) n − 1 m \times (m - 1) ^ {n - 1} m×(m−1)n−1, 总的数量是 m n m ^ n mn
那么 a n s = m n − m × ( m − 1 ) n − 1 = m × ( m n − 1 − ( m − 1 ) n − 1 ) ans = m ^ n - m \times (m - 1) ^ {n - 1} = m \times (m ^ {n - 1} - (m - 1) ^ {n - 1}) ans=mn−m×(m−1)n−1=m×(mn−1−(m−1)n−1)

算法步骤

实现上述公式即可, 注意输入的数据范围超过了 i n t int int, 输入的 n n n需要开long long

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MOD = 100003;

LL n, m;

LL q_pow(LL a, LL b, int MOD) {
   
    LL ans = 1;
    while (b) {
   
        if (b & 1) ans = ans % MOD * a % MOD;
        a = a % MOD * a % MOD;
        b >>= 1;
    }
    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> m >> n;
    LL ans = q_pow(m, n, MOD) - (LL) m % MOD * q_pow(m - 1, n - 1, MOD) % MOD;
    ans =  (ans % MOD + MOD) % MOD;

    cout << ans << '\n';
    return 0;
}