Skip to content

mod P

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

mod P

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
modP.js
modP.js
 
 
modP.py
modP.py
 
 

README.md

以下に、mod P 上での加算・減算・乗算に関するクエリ処理を、図とともに具体的かつ詳細に解説します。Node.js 実装内容に沿って、初期状態 → 各クエリ処理 → 結果出力までの流れを可視化していきます。

🔢 問題の流れ

入力:
P Q
q_1 Y_1
q_2 Y_2
...
q_Q Y_Q

例：

998244353 3
1 12
2 15
3 19

🎯 前提：mod P 上の演算とは？

mod P 上で演算とは、P で割った余りに置き換える操作。

例えば P=5 の場合：

操作式 通常の結果 mod 5 結果
3 + 4 7 2
3 × 4 12 2
1 - 3 -2 3

負の数が出る場合は、(負数 + P) % P で正の結果にします。

🎲 初期状態

P = 998244353
Q = 3
X = 1 (初期値)

🔁 クエリ処理の図解と解析

✅ クエリ1: 1 12 → X = X + 12

Before Operation After
X = 1 X + 12 = 13 13 % P = 13

📘 1 + 12 = 13, 13 < P → そのまま 13

🟩 出力：13

✅ クエリ2: 2 15 → X = X - 15

Before Operation After
X = 13 X - 15 = -2 (-2 + P) % P = 998244351

📘 13 - 15 = -2, 負なので -2 + P = 998244351

🟩 出力：998244351

✅ クエリ3: 3 19 → X = X × 19

Before Operation After
X = 998244351 X × 19 = 18966642669 18966642669 % P = 998244315

📘 998244351 × 19 = 18966642669

18966642669 ÷ 998244353 ≈ 18.99...
18966642669 % 998244353 = 998244315

🟩 出力：998244315

🧮 総まとめ図（各クエリの流れ）

初期状態: X = 1
        ↓
クエリ1: X = X + 12
        → X = 13
        → 出力: 13
        ↓
クエリ2: X = X - 15
        → X = -2 → (X + P) % P = 998244351
        → 出力: 998244351
        ↓
クエリ3: X = X × 19
        → X = 998244351 × 19 = 18966642669
        → X % P = 998244315
        → 出力: 998244315

🧪 性能測定のしくみ（図）

Node.js におけるパフォーマンス測定方法：

process.hrtime.bigint()     ← 高精度タイマー（ナノ秒）
process.memoryUsage().rss   ← 常駐メモリ（バイト単位）

処理開始 ─▶ 処理中（Q回繰り返し） ─▶ 結果出力
       ↑                                 ↓
   startTime                         endTime
        └─────▶ 実行時間 = end - start

メモリ使用量 = process.memoryUsage().rss / 1024 / 1024 (MB)

🧠 補足：なぜ BigInt を使うのか？

  • JavaScript の Number 型は IEEE 754 形式の浮動小数点数で、53ビットまでしか正確に扱えません。
  • 本問題の P ≈ 10^9、最大掛け算は P × P ≈ 10^18 に近づくため、BigInt が必須。

✅ 結論

この問題は Rolling Hash の土台となるmod 演算の性質理解と高速処理の実装練習です。

学びポイント：

  • mod P の演算：加算・減算・乗算
  • 負数 → 正の値に直す (a + P) % P
  • BigInt による精度保持
  • fs と process で高速 I/O とパフォーマンス計測