题目链接
bzoj1008: [HNOI2008]越狱
题解
补集转化 变为所有可能 (\(m^n\))减去一定越狱可能(\(m * (m-1) ^ {n - 1}\)) 然后就是一个快速幂了 话说这题学过乘法原理的都会做吧？ 取模有毒，WA十数发
代码
#include<cstdio>
#include<algorithm>
#define LL long long
#define mod 100003
LL a,b;
LL qpow(LL x,LL b) {
LL ret = 1;x %= mod;
for(;b;x = x * x % mod, b >>= 1) {
if(b & 1) ret = ret * x % mod;
}
return ret;
}
int main() {
LL n,m;
scanf("%lld%lld",&m,&n);
printf("%lld\n",(qpow(m,n) - m * qpow((m - 1),n - 1) + mod) % mod);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/9008667.html
