[BZOJ1008]&&[HNOI2008] 越狱

2014-09-04
竞赛题解 / 数论
BZOJHNOI快速幂排列

描述 Description

监狱有连续编号为 1…N 的 N 个房间，每个房间关押一个犯人，有 M 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱.

输入格式 InputFormat

输入两个整数 M，N.1<=M<=108,1<=N<=1012.

输出格式 OutputFormat

可能越狱的状态数，模 100003 取余.

样例输入 SampleInput

9999999 99999999999

样例输出 SampleOutput

11182

数据范围和注释 Hint

6 种状态为(000)(001)(011)(100)(110)(111).

​

BZOJ 1008

代码 Code

考虑不越狱的情况，即任意两间相邻的房间不信仰同种宗教，易得有 (m(m-1)^{n-1}) 种情况。则用快速幂求答案为(m^{n}-m(m-1)^{n-1})。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
const ll mod=100003;
ll i,j,t,n,m,l,r,k,z,y,x;
inline void read(ll &x)
{
    x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
ll qpow(ll a,ll b)
{
    ll c=1;
    while (b)
    {
        if (b&1) c=((ll)c*a)%mod;
        a=((ll)a*a)%mod;
        b=b>>1;
    }
    return c;
}
ll ans;
int main()
{
    read(m);read(n);
    ans=(qpow(m,n)%mod-(m*qpow(m-1,n-1))%mod)%mod;
    if (ans<0) ans+=mod;
    printf("%lld\n",ans);
    return 0;
}