BZOJ1008

摘要：有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 }