C++

bzoj1008 [HNOI2008]越狱


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

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 }

 


作者:wfj_2048,发布于:2018/08/29
原文:https://www.cnblogs.com/wfj2048/p/6416579.html