欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ1008

程序员文章站 2022-06-30 08:55:42
摘要:有n个犯人,被关在n个不同的房间,有m种宗教,如果,相邻房间的犯人信仰相同,则判定为越狱。那么我们可以用组合数学来计算这个数据,用方案的总数,减去不可能的情况,就是答案。 方案的总数:m^n ,在每个房间,每个宗教的可能有m种,有n个房间所以 m^n 不可能的情况: m * (m-1 ) ^( ......

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