![bzoj1008 [HNOI2008]越狱 bzoj1008 [HNOI2008]越狱](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
1008: [HNOI2008]越狱
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 5099 Solved: 2207
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)
Source
大意:给N个格子,M种颜色,给这些格子染色,问使这N个格子,存在相邻两个格子颜色相同的方案数
分析:简单明了,简单异常
首先一共有M^N种方式染色
使相邻格子颜色不同的方案有M*(M-1)^(N-1)种(第一位有M种选择,后面每位都只有M-1种选择)
然后相邻格子颜色不相同的方案:M^N - M*(M-1)^(N-1)
最后提醒:注意因为是快速幂取模,所以答案有可能为负数,要修正为正数
综上所述,本题得解
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
using namespace std;
typedef long long LL;
typedef double DB;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((bnt) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair
inline void SetIO(string Name) {
string Input = Name+".in",
Output = Name+".out";
freopen(Input.c_str(), "r", stdin),
freopen(Output.c_str(), "w", stdout);
} const LL Mod = ;
LL N, M;
LL All, Impossible, Possible; inline void Input() {
cin>>M>>N;
} inline void Multiply(LL &A, LL B) {
A = (A*B)%Mod;
} inline LL Power(LL Basic, LL Tim) {
LL Ret = ;
Basic %= Mod;
while(Tim) {
if(Tim&) Multiply(Ret, Basic);
Multiply(Basic, Basic), Tim >>= ;
}
return Ret;
} inline void Solve() {
if(N == ) {
cout<<M<<endl;
return;
} All = Power(M, N);
Impossible = Power(M-, N-);
Multiply(Impossible, M);
Possible = All-Impossible;
Possible = ((Possible%Mod)+Mod)%Mod; cout<<Possible<<endl;
} int main() {
SetIO("");
Input();
Solve();
return ;
}