bzoj1008 [HNOI2008]越狱

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

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 ;

 }

秒客网