BZOJ 1008 题解
problem
1008: [HNOI2008]越狱
Time Limit: 1 Sec Memory Limit: 162 MB
Description
监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果
相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
Input
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
Output
可能越狱的状态数，模100003取余
Sample Input
2 3
Sample Output
6
HINT
6种状态为(000)(001)(011)(100)(110)(111)
这就是一道数学题，需要写快速幂：
long long fast_mi(long long a,long long b)
{
if(b==0)
return 1;
if(b&1)
{
return (a*fast_mi(a,b-1));
}
else
{
return (fast_mi(a*a,b/2));
}
}
然后就是一个组合数学的问题了。我们考虑到可以越狱的情况太多了，实在难以计算。 所以不如直接用所有情况减去不能越狱的情况。
我们不难得出一个结论：所有的可能情况个数为m^n；要使得每个相邻的人的情况各不相同有m*(m-1)^(n-1)种，所以答案为 m^n-m*(m-1)^(n-1)。
#include <iostream>
using namespace std;
int mod=100003;
long long fast_mi(long long a,long long b)
{
if(b==0)
return 1;
if(b&1)
{
return (a%mod*fast_mi(a,b-1))%mod;
}
else
{
return (fast_mi(a*a%mod,b/2))%mod;
}
}
long long m,n;
int main()
{
cin>>m>>n;
cout<<(fast_mi(m,n)%mod-m%mod*fast_mi(m-1,n-1)%mod+mod)%mod;
return 0;
}
注意：不要忘了答案小于0时要加上100003再模。
