首页 > > 程序设计 > C/C++ >

bzoj1008 [HNOI2008]越狱

2018-06-17 23:21:00来源：未知阅读 ()

Description

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

Input

　　输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

Output

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

Sample Input

2 3

Sample Output

HINT

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

正解：组合数学+快速幂。

直接用总数减去不合法方案，答案为$m^n-m*(m-1)^{n-1}$。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define rhl 100003
14 #define inf 1<<30
15 #define il inline
16 #define RG register
17 #define ll long long
18  
19 using namespace std;
20  
21 ll m,n;
22  
23 il ll gi(){
24     RG ll x=0,q=0; RG char ch=getchar();
25     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if (ch=='-') q=1,ch=getchar();
26     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q ? -x : x;
27 }
28  
29 il ll qpow(RG ll a,RG ll b){ RG ll ans=1,x=a; while (b){ if (b & 1) ans=ans*x%rhl; x=x*x%rhl,b>>=1; } return ans; }
30  
31 il void work(){ m=gi(),n=gi(); printf("%lld",(qpow(m,n)-qpow(m-1,n-1)*m%rhl+rhl)%rhl); return; }
32  
33 int main(){
34     work();
35     return 0;
36 }