C - (Many Queries)^{-1}

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

概要

入力のパターンに限りがあるので,前計算をしておきましょう!

問題原案:tnodino
改題:uni_kakurenbo

解説

「非負 kk を無作為に選んだとき,3kmod9982443533^k \bmod 998244353 の値は平均して 99824435325×108\frac{998244353}{2} \backsimeq 5 \times 10^8 くらいになるだろう」という予想がつきます.(実際,33998244353998244353 の原始根であるので正しいです.)

さらに,5×108×105>2453×10135 \times 10^8 \times 10^5 > 2^{45} \backsimeq 3 \times 10^{13} であるので,だいたい答えは 10510^5 以下程度には収まるのではないか,という予想も立てられます.

コードを書いて試してみると,実際に q>70436q > 70436x245x \geq 2^{45} となることがわかります.

ですから,これらの値をすべて Φ\Phi 個のテストケースを処理する前に求めておいて,辞書などで保存しておくことで十分高速にこの問題を解決できることがわかります.

解説:uni_kakurenbo

実装例

Python