bzoj 1008: [HNOI2008]越狱(对立事件，组合数学)
1008: [HNOI2008]越狱
Time Limit: 1 Sec Memory Limit: 162 MB Submit: 8165 Solved: 3486 [Submit][Status][Discuss]
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/* ***********************************************
2Author :111qqz
3Created Time :2016年11月28日 星期一 16时23分38秒
4File Name :code/bzoj/1008.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const LL mod =100003;
34LL ksm( LL a,LL b,LL k)
35{
36 LL res = 1;
37 while (b>0)
38 {
39 if (b&1) res = (res * a)%k;
40 b = b >> 1LL;
41 a = (a*a)%k;
42 }
43 return res;
44}
45LL n,m;
46int main()
47{
48 #ifndef ONLINE_JUDGE
49 freopen("code/in.txt","r",stdin);
50 #endif
51 cin>>m>>n;
52 LL ans =ksm(m,n,mod)-m%mod*ksm(m-1,n-1,mod)%mod;
53 ans %=mod;
54 ans +=mod;
55 ans %=mod;
56 cout<<ans<<endl;
57
58
59 #ifndef ONLINE_JUDGE
60 fclose(stdin);
61 #endif
62 return 0;
63}