[HNOI2008] 越狱快速幂

2024-09-05 03:06:13

[HNOI2008] 越狱快速幂

水。考虑不发生越狱的情况：即宗教相同的都不相邻，一号任意放\(m\)种宗教的人，此后\(n-1\)个房间都放与上一个宗教不同的人，有\(m-1\)种，所以共有\(m*(m-1)^{n-1}\)种。答案即\(m^n-m*(m-1)^{n-1}\)。快速幂即可。

注意，这里需要考虑模后相减为负的情况，此时将负值再加上模数变为正数即可。

#include <cstdio>

#define MOD 100003

#define ll long long

using namespace std;

ll m,n;

ll qpow(ll x, ll k){

    ll ans=1;

    while(k){

        if(k&1) ans=ans*x%MOD;

        k>>=1;

        x=x*x%MOD;

    }

    return ans;

}

int main(){

    scanf("%lld %lld", &m, &n);

    m%=MOD;

    printf("%lld\n", (qpow(m, n)-qpow(m-1, n-1)*m%MOD+MOD)%MOD);

    return 0;

}

最新文章

热门文章