a^2[i] = a[i] [yukicoder No.573] - はまやんはまやんはまやん

前提知識

mod素数上でのaCb、累乗の高速計算

解法

https://yukicoder.me/submissions/208117

問題をグラフの問題に読み変えて考えてみる。
この問題は1～Nの各頂点から1つずつ有向辺を作る組み合わせ数を求める問題となる。
正しい有向辺の条件は、
1. 自分に遷移する
2. 遷移先が自分に遷移する有向辺を持っている
のいずれかを満たす必要がある
　
この組み合わせを計算する場合は、自分に遷移する頂点の個数毎に計算して足し合わせる。
自分に遷移する頂点がi頂点あるとする。
自分に遷移する頂点を決める組み合わせはaCb(N, i)である。
そして、遷移先が自分に遷移する有向辺を持っている頂点はN-i個あり、それぞれi通りの遷移先があるので、こちらの組合せはi^(N-i)となる。
これをかけ合わせると自分に遷移する頂点がi頂点あるときの組合せとなる。
あとは、これを全て合計すると答え。

int N;
Comb<mint, 101010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    mint ans = 0;
    rep(i, 1, N + 1) {
        mint a = com.aCb(N, i);
        mint b = mint(i) ^ (N - i);
        mint d = a * b;
        ans += d;
    }
    cout << ans << endl;
}