Nowhere P [第二回日本最強プログラマー学生選手権 D]

https://atcoder.jp/contests/jsc2021/tasks/jsc2021_d

解説

https://atcoder.jp/contests/jsc2021/submissions/21831261

まず、10⁹+7 modライブラリを持ってない場合はAtCoder Libraryを使おう。

今回の問題はNもPも上限が10⁹（intの最大を狙って良く使われる上限）となっている。
よって、何かの全探索で解くのは難しそうである。
なので、数学的に計算できないかをまずは初手考える。

先頭から数を決めていくことを考える。
問題の条件的に先頭から数を決めていけば1つずつPの倍数でない条件を満たして行けそうな感じがする。
一番最初は1～P-1のどれでもよいのでP-1通りである。
次は、1～P-1のどれでもよいのだが、1つだけ足すとこれまでの和がPの倍数になってしまうものがある。
なのでそれだけ使用できないためP-2通りとなる。
その次も実は同様の状況であり、P-2通りである。
…

よって最初の1つ目はP-1通りで、それ以降のN-1個はP-2通り。
答えは(P-1)(P-2)^N-1となる。
これをmint(素数modライブラリ)で答え。

素数mod系の基礎理論は知っていると一部応用できる（二乗法とか）ため、学んでおくとよい。
https://blog.hamayanhamayan.com/entry/2018/06/06/210256
けんちょんとかの方が分かりやすいかも。

int N, P;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> P;

    mint ans = mint(P - 1) * (mint(P - 2) ^ (N - 1));
    cout << ans << endl;
}