upd:2020.9.01

题目描述

监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。

有 m 种宗教，每个犯人可能信仰其中一种。

如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。

求有多少种状态可能发生越狱。

分析

正着不行那就反向思考,即有多少种不会发生越狱的情况,对于第一个人，有m种，之后呢因为不能和前面相

同，所以只有m-1种，总方案数减去不能越狱的方案数就是答案了

C++ 代码

#include<bits/stdc++.h>
#define ll long long
#define MOD 100003
using namespace std;
ll n,m;

inline ll quickpow(ll m,ll n){
    ll ans=1;
    for (;n;n>>=1){
        if(n&1) ans=(ans*m)%MOD;
        m=m*m%MOD;
    }
    return ans;
}

int main(){
    scanf("%lld%lld",&m,&n);
    ll zong=quickpow(m,n);
    ll x1=m*quickpow(m-1,n-1)%MOD;

    printf("%lld\n",(zong-x1+MOD)%MOD);
}