https://yukicoder.me/problems/no/573
前提知識
解法
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; }