题目描述

监狱有 n 个房间,每个房间关押一个犯人,有 m 种宗教,每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。

答案对 100,003 取模。

输入格式

输入只有一行两个整数,分别代表宗教数 m 和房间数 n。

输出格式

输出一行一个整数代表答案。

输入输出样例

输入 #1

2 3

输出 #1

6

说明/提示

样例输入输出 1 解释

状态编号 1 号房间 2 号房间 3 号房间
1 信仰 1 信仰 1 信仰 1
2 信仰 1 信仰 1 信仰 2
3 信仰 1 信仰 2 信仰 2
4 信仰 2 信仰 1 信仰 1
5 信仰 2 信仰 2 信仰 2
6 信仰 2 信仰 2 信仰 1

数据规模与约定

对于 100% 的数据,保证 1m1081n10121 \le m \le 10^8,1 \le n \le 10^{12}

题目分析

本道题目要求的是可能发生越狱的情况。什么情况下会发生越狱呢?“如果相邻房间的犯人的宗教相同,就可能发生越狱”。如果正面思考相邻的情况,由于宗教数量m的不确定性,会有多种可能。此时可以反着思考,利用容斥的性质,相邻的情况=所有情况不相邻的情况相邻的情况=所有情况-不相邻的情况

所有情况:mnm^n ,不相邻的情况:m×(m1)n1m\times (m-1)^{n-1}

由于m和n会很大,那么利用快速幂技巧,快速求出幂次方,并利用同余的性质,在过程中边计算,边取余。

易坑点

需要注意,取余后相减会出现结果小于零的情况。

处理方式(a%M-b%M+M)%M

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int M=1e5+3;
//所有可能-互不相邻的可能
ll mypow(ll a,ll x){//快速幂求 a^x
	if(x==0) return 1%M;
	ll tmp=mypow(a,x/2);
	if(x&1) return (tmp*tmp%M)*a%M;
	return tmp*tmp%M;
}
int main(){
	ll n,m;
	cin>>m>>n;
	cout<<(mypow(m,n)%M-m*mypow(m-1,n-1)%M+M)%M;//注意取余后相减可能小于零
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)