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 }