摘要：有n个犯人，被关在n个不同的房间，有m种宗教，如果，相邻房间的犯人信仰相同，则判定为越狱。那么我们可以用组合数学来计算这个数据，用方案的总数，减去不可能的情况，就是答案。
方案的总数：m^n ，在每个房间，每个宗教的可能有m种，有n个房间所以 m^n
不可能的情况： m * (m-1 ) ^(n-1) ，我们要达成不可能的情况，必须要选中一种宗教m[ i ] ，而其他的房间宗教与被选中的宗教不同, ，这样才可能发生越狱的情况，所以，我们假设某个房间有m种选择，其他的房间为 （m-1)^(n-1) 剩余宗教数 ^ 剩余房间数。
答案： 方案的总数 - 不可能的方案 = 可能越狱的方案
由于方案最终的数量可能过于庞大，因此，在这个计算的过程中用到快速幂的技巧来实现。
ll pow( ll x, ll y)
{
ll ans=1 ,a=x;
while(y)
{
if(y&1) ans*=a, ans%=p;
a*=a ,a%=p;
y>>=1;
}
return ans;
}
我要评论 1 #include<iostream>
2 using namespace std;
3 typedef long long ll;
4 const int p=100003;
5 ll pow(ll x, ll y)
6 {
7 ll a=x,ans=1;
8 while(y)
9 {
10 if(y&1)ans*=a,ans%=p;
11 a*=a,a%=p;
12 y>>=1;
13 }
14 return ans;
15 }
16 int main()
17 {
18 ll n,m;
19 while(cin>>m>>n)
20 {
21 m%=p;
22 ll ans=pow(m,n);
23 ans-=pow(m-1,n-1)*m;
24 ans = ((ans%p)+p)%p;
25 cout<<ans<<endl;
26 }
27 return 0;
28 }
如对本文有疑问， 点击进行留言回复！！
网友评论