侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【快速幂, 数学】越狱

GabrielxD
2023-03-21 / 0 评论 / 0 点赞 / 117 阅读 / 582 字
温馨提示:
本文最后更新于 2023-03-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1290. 越狱 - AcWing题库


监狱有连续编号为 11nnnn 个房间,每个房间关押一个犯人。

mm 种宗教,每个犯人可能信仰其中一种。

如果相邻房间的犯人信仰的宗教相同,就可能发生越狱。

求有多少种状态可能发生越狱。

输入格式

共一行,包含两个整数 mmnn

输出格式

可能越狱的状态数,对 100003100003 取余。

数据范围

1m1081 \le m \le 10^8 ,
1n10121 \le n \le 10^{12}

输入样例:

2 3

输出样例:

6

样例解释

所有可能的 66 种状态为: (000)(001)(011)(100)(110)(111)(000)(001)(011)(100)(110)(111)

解题

方法一:快速幂

思路

对于每一个犯人来说,他都能选择 mm 种宗教,所以 nn 个犯人一共会有 i=1nm=nm\prod_{i=1}^n{m} = n^m 种状态。

若想不发生越狱,对于第 11 个房间的犯人,没有人在他左边与其相邻,所以他选择 mm 种宗教都不会与人发生越狱;对于第 2n2 \sim n 个房间的犯人 ii ,他们都不能选择与犯人 i1i-1 相同的宗教,所以只有 m1m-1 种宗教供他们选择。那么 nn 个犯人共有 mi=2nm=m(m1)n1m \cdot \prod_{i=2}^{n}{m} = m \cdot (m-1)^{n-1} 种状态。

综上,共有 nmm(m1)n1n^m - m \cdot (m-1)^{n-1} 种状态可能发生越狱。

数都比较大,所以用快速幂来取幂。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 100003;
    
    static long qmi(long base, long exp) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        long m = in.nextLong(), n = in.nextLong();
        long total = qmi(m, n);
        long not = (m * qmi(m - 1, n - 1)) % MOD;
        System.out.println((total - not + MOD) % MOD);
    }
}
0

评论区