【题解】越狱

题目描述

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

答案对 100,003 取模。

输入格式

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

输出格式

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

输入输出样例

输入 #1

2 3

输出 #1

6

说明/提示

样例输入输出 1 解释

数据规模与约定

对于 100% 的数据，保证

。

题目分析

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

所有情况：

不相邻的情况：

由于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.