首页 > 代码库 > BZOJ 1008 HNOI2008 越狱 快速幂
BZOJ 1008 HNOI2008 越狱 快速幂
题目大意:有三名越狱犯杀死狱警后穿警服逃狱,现已被警方全部抓获……啊呸呸呸呸呸,扯远了
监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱
m<=10^8,n<=10^12
一看这数据范围就是logn嘛!于是我们来分析一下
f[i]表示连续i个房间可能发生越狱的情况数
当状态从f[i]转移到f[i+1]时有两种情况:
1.原先状态就会发生越狱 那么我们再塞一个人进去也一定会发生越狱 情况数为f[i]*m
2.原先状态不会发生越狱 那么我们只有塞进去一个与旁边人信仰相同的人才会越狱 情况数为m^i-f[i]
故得到递推式 f[i+1]=f[i]*(m-1)+m^i
这一看就是矩阵乘法!麻烦!不会写!妈蛋!
我们换一个思路,求一下补集
f[i]表示连续i个房间无法发生越狱的情况数
当状态从f[i]转移到f[i+1]时有两种情况:
1.原先状态就会发生越狱 那么我们再塞一个人进去也一定会发生越狱 情况数为0
2.原先状态不会发生越狱 那么我们只有塞进去一个与旁边人信仰不同的人才不会发生越狱 情况数为f[i]*(m-1)
故f[i+1]=f[i]*(m-1)初值f[1]=m,最后得到结果用m^n相减即可
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 100003ll using namespace std; typedef long long ll; ll m,n,ans; ll ksm(ll x,ll y) { ll re=1; while(y) { if(y&1)re*=x,re%=M; x*=x,x%=M; y>>=1; } return re; } int main() { cin>>m>>n; m%=M; ans=ksm(m,n); ans-=m*ksm(m-1,n-1); ans%=M; ans+=M; ans%=M; cout<<ans<<endl; }
BZOJ 1008 HNOI2008 越狱 快速幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。