E - Integer Sequence Fair

・問題URL

https://atcoder.jp/contests/abc228/tasks/abc228_e

・思考

・配列の個数はK^N個、点数の付け方それぞれの配列にM通り、あれ？答えMのK^N乗じゃね？(本番はこれからです…)

・キーワード

・繰り返し二乗法
・フェルマーの小定理

・解法

・以下P=998244353とする。
・M^(K^N)modP≠M^((K^N)modP)modPじゃないので。
・M%P=0のとき、答え0。
・そうじゃないとき、この時に限ってフェルマーの小定理が使える。指数書くのめんどいので省略するが、M^(K^N)modP＝M^((K^N)mod(P-1))modPになるから、(K^N)mod(P-1)とM^XmodPが求められれば良い。繰り返し二乗法を、法をP-1,Pと変えて二発かまそう。(以下のコードは、mod1が998244352、mod2が998244353を法にしたもの。)
・ネットで拾ったライブラリ使ったらオーバーフローした。絶対に許さない。

・コード

int main() {

   ll N, K, M;
   cin >> N >> K >> M;
   if (M % 998244353 == 0)cout << 0 << endl;
   else {
       ll A = pow_mod1(K, N);
       ll B = pow_mod2(M, A);
       cout << B % 998244353 << endl;
   }
}