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)
/* ***********************************************
Author :111qqz
Created Time :2016年11月28日 星期一 16时23分38秒
File Name :code/bzoj/1008.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const LL mod =100003;
7LL ksm( LL a,LL b,LL k)
8{
9 LL res = 1;
10 while (b>0)
11 {
12 if (b&1) res = (res * a)%k;
13 b = b >> 1LL;
14 a = (a*a)%k;
15 }
16 return res;
17}
18LL n,m;
19int main()
20{
21 #ifndef ONLINE_JUDGE
22 freopen("code/in.txt","r",stdin);
23 #endif
24 cin>>m>>n;
25 LL ans =ksm(m,n,mod)-m%mod*ksm(m-1,n-1,mod)%mod;
26 ans %=mod;
27 ans +=mod;
28 ans %=mod;
29 cout<<ans<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}