Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 228 E 問題 Integer Sequence Fair

AtCoder ABC ABC228 E問題 500 pts

問題

提出解答

問題の概要

正の整数 $L$ に対して, $[\![L]\!]$ で $1$ 以上 $L$ 以下の整数全体の集合とする. 集合 $\operatorname{Map}([\![K]\!] ^N, [\![M]\!])$ の濃度 (元の個数) を $998244353$ で割った余りを求めよ.

制約

$1 \leq N,K,M \leq 10^{18}$
入力は全て整数である.

解法

以降では, 説明のために, 整数 $a,b$ に対して, $\operatorname{pow}(a,b):=a^b$ とする.

$\# \operatorname{Map}([\![K]\!] ^N, [\![M]\!])=\operatorname{pow} \left(\# [\![M]\!],\# [\![K]\!] ^N \right)=\operatorname{pow}(M,K^N)$ である. よって, 求めるべき値は, $\operatorname{pow}(M,K^N) \pmod{998244353}$ である.

ここで, $\operatorname{pow}(a,b):=a^b \pmod{m}$ を求めるためには, 繰り返し二乗法によって, $O(\log b)$ で求められるが, 今回の問題では絶望的である. そこで, この問題では $998244353$ の性質を利用する.

$998244353$ は素数である. ここで, 素数の剰余において, 以下の重大な定理がある.

Fermat's Little Theorem

素数 $p$ と, $p$ の倍数でない任意の整数 $a$ において,

$a^{p-1} \equiv 1 \pmod{p}$

が成り立つ.

よって, 定理の適用条件に注意することして, 以下のような解法になる ( $P=998244353$ とする).

$M \equiv 0 \pmod{P}$ ならば, $K^N \geq 1$ なので, $\operatorname{pow}(M,K^N) \equiv \operatorname{pow}(0,K^N) \equiv 0 \pmod{P}$ である.
$M \not \equiv 0 \pmod{P}$ ならば, $\alpha:=K^N \pmod{(P-1)}$ とすることにすると, Fermat's Little Theorem から, $\operatorname{pow}(M,K^N) \equiv \operatorname{pow}(M, \alpha) \pmod{P}$ である.

計算量は, 繰り返し二乗法によって, $O(\log N+\log P)$ である.