考察
長さNの整数列は各要素にK通りの選択肢があるためK^N通りあり、それぞれにM通りの点数を独立に付けられる。したがって求める個数は M^(K^N) だが、N・K・Mが10^18以下なので指数そのものは構成できない。
法P=998244353は素数である。底MがPの倍数でなければFermatの小定理により指数をP-1で割った余りだけ求めればよい一方、MがPの倍数なら同じ簡約をしてはいけない。
棄却する候補: K^Nを通常の整数として計算してから、Mをその回数だけ掛ける。
指数は入力の時点で10^18乗まで膨らみ、値の保持も回数分の反復もできない。
採用する候補: M mod Pを場合分けし、非零ならK^N mod (P-1)を高速冪で求め、その値を指数としてMの高速冪を計算する。
Fermatの小定理で巨大指数をP-1周期へ落とせ、二段の高速冪はいずれも指数のビット数に比例する反復で済む。
M≡0 (mod P) のとき指数K^Nは正なので答えは0である。この場合に指数をP-1で簡約すると、余り0から誤って0^0を扱う可能性があるため先に分岐する。
MとPが互いに素なら M^(P-1)≡1 (mod P) なので、K^NをP-1で割った商の分は全て消え、余りだけが結果を決める。
M mod P=0なら0を出力する。そうでなければ二分累乗法で e=K^N mod (P-1) を計算し、続けて M^e mod P を計算する。
典型の発動条件
Fermatの小定理による指数の簡約
発動条件: 素数法Pの下で、Pと互いに素な底を巨大な指数へ累乗したいとき。
指数K^NをP-1で割った余りへ置き換え、外側の累乗を計算可能な大きさにする。
二分累乗法
発動条件: 指数が非常に大きく、累乗を剰余付きで求めたいとき。
K^N mod (P-1) と M^e mod P の両方を、指数を2進展開して計算する。
問題固有の要素
指数をP-1で簡約できるかは、外側の底MがPと互いに素かで決まり、内側の底Kとは無関係である。
別の問題へ持ち帰る視点: 累乗塔を剰余で扱うときは、各段で使う周期の前提を底ごとに確認し、0や非互いに素の例外を先に分離する。
正当性
個数はM^{K^N}。MがPの倍数なら正の指数のため答え0。それ以外はFermatの小定理により指数をP−1で割った余りへ替えられる。二段の高速冪はその余りと最終値を正確に求める。
実装上の注意
- MをPで割った余りが0かを指数簡約より先に判定し、二つの高速冪で法P-1と法Pを取り違えない。
復習の核
- 『指数はP-1で割ればよい』だけで済ませず、その根拠がM≠0 (mod P) に依存することと、M≡0の場合の指数が正であることを別々に説明する。
計算量と制約
時間
O(log N+log P)、P=998244353。
空間
O(1)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N, K, M \leq 10^{18}; N, K, and M are integers.
出典