首页 > 其他 > 详细

[bzoj1008] [HNOI2008]越狱

时间:2019-02-03 15:46:06      阅读:177      评论:0      收藏:0      [点我收藏+]

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

Solution

总方案数减去不可越狱的方案数即可。

答案就是:
\[ ans=m^n-m\cdot (m-1)^{n-1} \]

#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

#define write(x) printf("%d\n",x)

const int maxn = 2e5+10;
const int mod = 100003;

int n,m;

int qpow(int a,int x) {
    int res=1;a%=mod;
    for(;x;x>>=1,a=a*a%mod) if(x&1) res=res*a%mod;
    return res;
}

signed main() {
    read(m),read(n);
    write((qpow(m,n)-m%mod*qpow(m-1,n-1)%mod+mod)%mod);
    return 0;
}

[bzoj1008] [HNOI2008]越狱

原文:https://www.cnblogs.com/hbyer/p/10350437.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!