M_sea

洛谷3197 [HNOI2008]越狱
题目描述监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻...
扫描右侧二维码阅读全文
30
2017/09

洛谷3197 [HNOI2008]越狱

题目描述

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

传送门

算法

这道题是一道计数问题。

越狱的状态数不好直接求出,所以考虑:越狱状态数=总状态数-不越狱状态数。
总状态数很好求,即$m^n=m*m^{n-1}$

不越狱状态数可以这么考虑:任意两个相邻房间非同一宗教,则只需满足每一个房间与前一个房间的宗教不同即可。
所以不越狱状态数为$m*(m-1)^{n-1}$

用快速幂求出以上即可。注意负数处理。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
const int MOD=100003; //取模数
typedef long long LL;
inline LL fastpow(LL a,LL b) //快速幂模板
{
    if (b==1) return a%MOD; //一次方直接取模
    LL s=fastpow(a,b/2)%MOD; //缩小一半递归
    if (b&1) return (s*s%MOD)*(a%MOD)%MOD; //再乘上一个a
    else return s*s%MOD; //直接返回平方
}
int main()
{
    LL n,m;
    cin>>m>>n; //输入
    LL ans=(m%MOD)*((fastpow(m,n-1)+MOD*10-fastpow(m-1,n-1))%MOD)%MOD; //计算,MOD*10是为了防止负数
    cout<<ans<<endl; //输出
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 17 PM

发表评论