题意描述

监狱有连续编号为 $1 \dots n$ 的 $n$ 个房间，每个房间关押一个犯人。

一共有 $m$ 种宗教，每个犯人可能信仰其中一种。

如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

输入格式

输入仅有一行，包括两个整数 $m, n$ ，分别表示宗教数量与犯人数量。

输出格式

输出仅有一行，包含一个整数，表示可能越狱的状态数。

由于这个数可能比较大，因此，请输出该数模 $100003$ 取余的结果。

Input & Output ‘s examples

Input ‘s eg

markdown

2 3

Output ‘s eg

markdown

样例解释

6 种状态为 $(000)$ , $(001)$ , $(011)$ , $(100)$ , $(110)$ , $(111)$

数据范围和约定

对于 $30 %$ 的数据，保证 $1 \leq m, n \leq 1000$

对于 $100 %$ 的数据，保证 $1 \leq m \leq 10^{8}$ ， $1 \leq n \leq 10^{12}$

分析

真正的组合数学入门题……

尝试直接做，发现直接统计多少人越狱会很麻烦。

考虑容斥。很容易看出，越狱的方案数等于总共的方案数减去不会越狱的方案数。

由于每一个房间信仰的宗教有 $m$ 种可能，一共有 $n$ 个房间，因此，总方案数为 $m^{n}$ 。

现在考虑怎么样才不会越狱，显然，只有当两个房间信仰的宗教不同时才不会越狱。

也就是说，对于第一个房间，我们有 $m$ 种选择，而剩下的房间要保证与之前的房间不同，每一间都有 $(m - 1)$ 种可能。

综上，最终答案为 $m^{n} - m * (m - 1)^{n - 1}$ ，直接快速幂计算即可。

剩下的见代码即可 ~~(这题应该不用写注释了吧)~~

Code[Accepted]

cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long 
#define I inline
#define N 100001
#define HA 100003


using namespace std;

ll n , m;

ll Pow(ll a , ll n){
    if(n == 0) return 1;
    if(n == 1) return a;
    ll c = Pow(a , n >> 1) % HA;
    if(n % 2 == 0){
        return c * c % HA;
    }
    else{
        return ((c * c) % HA * a) % HA;
    }
}

int main(){
    cin >> m >> n;
    ll ans =  Pow(m , n) - m * Pow(m - 1 , n - 1) % HA;
    ans += HA;
    cout << ans % HA << "\n";
    return 0;
}