[洛谷 3197][HNOI2008]越狱

题目链接

https://www.luogu.org/problem/P3197

题解

考虑计算不越狱的方案数。

第一个人有 \(m\) 种信仰，后面每个人都有 \(m-1\) 种信仰，显然不越狱的方案数为 \(m \times (m-1)^{n-1}\) 种方案。

总方案数为 \(m^n\) 种，除去不越狱的剩下的显然都是越狱了。

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