[洛谷 3197][HNOI2008]越狱

题目链接

https://www.luogu.org/problemnew/show/P3197

题解

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

第一个人有\(m\)种信仰,后面每个人都有\(m-1\)种信仰,显然不越狱的方案数为\(m*(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;
}

 

发表评论

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