トヨタシステムズプログラミングコンテスト2021 (AtCoder Beginner Contest 228) E - Integer Sequence Fair (500)
整数列の個数は$ k^n個
ある数列に対しての点数の付け方は$ m通り
なので全体で求めたいのは$ m^{k^n} \bmod 998244353
フェルマーの小定理から$ m^{998244353-1} \bmod 998244353 \equiv 1
$ mを$ k^nを$ 998244353-1で割ったもの乗して$ 998244353で割れば良い
$ k^nが0になった場合は$ 998244353-1を足す
べき乗は繰り返し二乗法で高速に求められる
$ N乗なら$ \mathcal{O}(\log N)
問題: https://atcoder.jp/contests/abc228/tasks/abc228_e
提出: https://atcoder.jp/contests/abc228/submissions/27380464
#トヨタシステムズプログラミングコンテスト2021 #ABC228 #500pt #E #ABC #AtCoder
#フェルマーの小定理