[BZOJ1008][HNOI2008]越狱

题目大意

求解一个由 \(1 \cdots m\) 组成的长度为 \(n\) 的数列, 使得存在两个相邻的数是相同的的种数

思路

不妨从反面思考,答案就是总数减去两两不同的

#include <bits/stdc++.h>

typedef long long ll;
const int p = 100003;

ll qpow(ll x, ll y) {
    ll res = 1;
    for (; y; y >>= 1, x = x * x % p) if (y & 1) res = res * x % p;
    return res;
}

int main() {
    ll a, b; scanf("%lld %lld", &a, &b);
    printf("%lld", ((qpow(a, b) - (qpow(a - 1, b - 1) * a)) % p + p) % p);
}