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