1290. 越狱 (逆向思维)

分析：正向很难考虑，考虑逆向

逆向：有m种宗教，n个犯人

犯人所有宗教信仰的情况：m^n （m*m*m*...一共n次）

犯人宗教信仰不会越狱的情况：

• 第1个犯人可选宗教数为m
• 第二个犯人可选宗教数为m-1(左边选了什么，当前不能选...)

综上：所有会发生越狱的情况=所有情况-不发生越狱

=m^n-(m*(m-1)^(n-1))

#include <iostream>
#include <algorithm>
using namespace std;
const int mod=100003  ;
typedef long long ll;
 
ll qmi(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=1ll*res*a%mod;
        b>>=1;
        a=1ll*a*a%mod;
    }
    return res%mod;
}
 
int main()
{
    ll m,n;
    cin>>m>>n;
    ll a=qmi(m,n);
    ll b=1ll*m*qmi(m-1,n-1)%mod;
    cout<<(a-b+mod)%mod<<endl;
    
}