BZOJ1008: [HNOI2008]越狱(快速幂)

题目：

1008: [HNOI2008]越狱

解析：

水一发题解别的题太麻烦不想写，就写一下这种zz题
利用乘法原理，共有\(m^n\)种方法关押罪犯，使相邻的互不相同的方法有\(m*(m-1)^{n-1}\)
所以答案就是\(m^n-m*(m-1)^{n-1}\)

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 100003;

int n, m;

int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1, a = (a * a) % mod;
    }
    return ans;
}

signed main() {
    cin >> m >> n;
    int a = (qpow(m - 1, n - 1) * (m % mod)) % mod;
    cout << (qpow(m, n) - a + mod) % mod;
}

原文链接:https://www.cnblogs.com/lykkk/p/11402319.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有