水一篇数论题解

题目

P3197 [HNOI2008]越狱

题目描述

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

输入输出格式

输入格式：

输入两个整数 $M,N$

输出格式：

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

输入输出样例

输入样例#1：

1
2 3

输出样例#1：

1
6

思路

开始做这题是顺推，不太好想。

尝试反推。

可能发生越狱状态 = 全部状态-不可能发生越狱状态

于是问题变得清晰起来。

全部状态就是: $M^N$ (乘法原理)

而不可能发生越狱的状态就是: $M*(M-1) ^ {N-1}$(乘法原理)

取余后相减也许为负数所以对答案加上模数后再取模一次。

$(((ksm(m,n)-(m*ksm(m-1,n-1)))%MOD+MOD)%MOD)$

使用快速幂计算幂次即可。

Code

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
#include<cstdio>
#define ll long long
using namespace std;
inline ll read(){
    ll ans=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=ans*10+ch-48;ch=getchar();}
    return ans*f;
}
void write(ll x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar(x%10|48);
}
const int MOD=100003;
ll m,n;
inline ll ksm(ll a,ll b){
    ll ans=1,base=a;
    while(b){
        if(b&1){
            ans=(ans*base)%MOD;
        }
        base=(base*base)%MOD;
        b>>=1;
    }
    return ans;
}
int main(){
    m=read();
    n=read();
    write(((ksm(m,n)-(m*ksm(m-1,n-1)))%MOD+MOD)%MOD);
    puts("");
    return 0;
}