bzoj 1008

[HNOI2008]越狱

Description

监狱有连续编号为 $1 \dots N$ 的 $N$ 个房间，每个房间关押一个犯人，有 $M$ 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱.

Input

输入两个整数 $M, N$ . $1 \le M \le 10^8, 1 \le N \le 10^{12}$

Output

可能越狱的状态数，模 $100003$ 取余.

Sample Input

2 3

Sample Output

题解

所有可能的方案数为 $U = M^N$ .

考虑不会发生越狱的情况，也就是任意相邻两人的信仰不同. 第一个人有 $M$ 种选择方案，剩下的每个人只要与前一个不同就行，共 $(M-1)^{N - 1}$ 种方案. 于是不会发生越狱的方案数为 $A = M\cdot(M-1)^{N-1}$ .

最后答案就是 $U - A$ .

代码

#include <cstdio>

using namespace std;

typedef long long int ll;
const ll p = 100003ll;

void add(ll &dest, ll delta)
{
    dest += delta;
    if (dest < 0) dest += p;
    if (dest >= p) dest -= p;
}
void mul(ll &dest, ll times)
{
    dest *= times;
    dest -= dest / p * p;
}
ll qow(ll a, ll x)
{
    ll ret = 1ll;
    while (x)
    {
        if (1 & x) mul(ret, a);
        mul(a, a);
        x >>= 1;
    }
    return ret;
}

int main(void)
{
    ll M, N;
    scanf("%lld%lld", &M, &N);
    ll ans = qow(M, N);
    ll notans = qow(M - 1, N - 1);
    mul(notans, M);
    add(ans, p - notans);
    printf("%lld\n", ans);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# bzoj 1008

# [HNOI2008]越狱

# Description

# Input

# Output

# Sample Input

# Sample Output

# 题解

# 代码