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
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const LL mod =100003;
LL ksm( LL a,LL b,LL k)
{
    LL res = 1;
    while (b>0)
    {
	if (b&1) res = (res * a)%k;
	b = b >> 1LL;
	a = (a*a)%k;
    }
    return res;
}
LL n,m;
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	cin>>m>>n;
	LL ans =ksm(m,n,mod)-m%mod*ksm(m-1,n-1,mod)%mod;
	ans %=mod;
	ans +=mod;
	ans %=mod;
	cout<<ans<<endl;


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}