ABC 228 E — Integer Sequence Fair

考察

長さ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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Integer Sequence Fair の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 剰余周期と指数法則を利用する

主題
追加で学ぶ技能
既習技能
    なし

    主タグ: 法上の四則演算・高速累乗・逆元 剰余周期・指数法則

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 剰余周期と指数法則を利用する

    • 剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。
    • 剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。

    先に読む単元:

    この解説で扱わないこと:

    • 逆元・一次合同・CRTによる合同条件の統合、および巡回群の位数を使う計数。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題