题意:这个是中文,不用解释了吧。

因为每个人有m种宗教可以信仰,那么一共有m^n种排列情况。而不发生越狱的情况只能是,第一个人选择m的一种,第二个人有m-1种选择,后面为了不同,都是m-1种选择,共m*(m-1)^(n-1)种。由于幂太大,达到连大数都存不下了,所以这里需要用到快速幂来计算。快速幂其实就是把一个带幂的数拆分一下,幂为偶数的时候可以除一半,把底数多一个,奇数的时候先拆一个出来使幂变成偶数再计算:

blob.png

题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=3211

代码:

Memory: 1288 KB
Time: 0 MS
Language: C++
Result: Accepted
#include <iostream>
using namespace std;
#define LL long long
const LL mod = 100003;
int mmod(LL x, LL y)
{
    LL val=1;
    while(y){
        if(y%2)val = (val*x)%mod;
        x = (x*x)%mod;
        y/=2;
    }
    return val;
}
int main()
{
    LL m, n, ans;
    while(cin>>m>>n)
    {
        LL ans1=mmod(m, n);
        LL ans2=mmod(m-1, n-1);
        ans=(ans1-m*ans2)%mod;
        if(ans<0)ans+=mod;
        cout<<ans<<endl;
    }
    return 0;
}