欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-11-18 22:29:40
题目: "1008: [HNOI2008]越狱" 解析: 水一发题解~~别的题太麻烦不想写,就写一下这种zz题~~ 利用乘法原理,共有$m^n$种方法关押罪犯,使相邻的互不相同的方法有$m (m 1)^{n 1}$ 所以答案就是$m^n m (m 1)^{n 1}$ 代码: cpp include ......

题目:

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;
}