ARC 147 D - Sets Scores (700, 黄)

• 問題文
• 正解コード(C++)

お気持ち

• 小さいケースを全探索してOEISに投げれば解を予想できます。
• 対称性をいい感じに使うと、数え上げの空間が簡単になります。
• (良い行列, 良い選び方) を数える問題にして選び方を固定するのはよくあるテクニックですが、良い選び方になるように狙って行列を作らなくても、適当な行列を作ってXORで帳尻を合わせるなり、適当な行列を作った場合に良い選び方になる確率を考えるなりすればいいというのが、面白いところですね。

考察

解法1の概略

全単射の証明

確率を考える解法

ソースコード

#include <iostream>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
using mint = modint998244353;

int main() {
    int n, m;
    cin >> n >> m;
    mint ans = mint(m).pow(n - 1) * mint(n).pow(m);
    cout << ans.val() << endl;
    return 0;
}