传送门= ̄ω ̄=

思路

排列组合……首先我们可以算出不能越狱有多少种情况:第一个房间有m种可能(宗教),第二个房间因为不可以发生越狱,所以不能和第一个房间一样,所以是有(m-1)种可能,第三个房间同理,也是(m-1)种可能,以此类推。所以不能越狱共有:m×(m-1)^(n-1) 种可能。而总共有m^n种可能,所以最终答案为m^n-m×(m-1)^(n-1) 。

所以很明显,用快速幂就行了,记得取膜。最后做减法可能会减出负数,所以要把答案加上100003再取膜。

还有!要开long long!

代码

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

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *