初めて TechFUL に参加してみたんですが、1 位でスイッチ lite がもらえることになったみたいで嬉し～なのいみです。

割と簡単(青 diff くらい？)めの問題が多かった印象ですが、この「羽根つき」の問題だけ少し難しめに感じました。解説の計算量は $O(N ^ {2} 2 ^ N)$ らしいですが、 $O(N 2 ^ N)$ で解けたので簡単に解法を紹介しようと思います。

問題

$N$ 戦先取の羽根つきを A, B の二人で行う。 $A_i$ 対 $B_i$ になったら B の勝ち、というルールが $M$ 個提案されている。 A が勝つような試合の通り数が奇数になるようなルールの選び方を $998244353$ で割った余りを求めよ。 $N \le 17$ 問題リンク

解法

斜めに bit dp をしながら見ていきます。 $dp _ {i, b} = (i 試合後に A が j ( \in b ) 勝しているような通り数が奇数となるルールの選び方の通り数)$ とします。

$dp _ i$ から $dp _ {i + 1}$ を追加ルールを一切追加しないものとして求めた後に追加ルールを適用することを考えます。

この場合の DP は簡単に求まります(A が勝つか負けるかで場合分け)。ただし、A が N 勝している、というケースは場合分けする必要があることに注意してください。

追加ルールについて処理をします。 $dp _ {i, b}$ についてルールを追加することは、 $b$ のルールに対応する勝敗の組み合わせが奇数ならば偶数にすること (bit が立っていれば 0 にすること) に対応します。

$b$ において、ルールに対応する勝敗の組み合わせが奇数の(bit が立っている)個数を $s$ 個、偶数の個数を $t$ 個とします。ルール $2 ^ {s + t}$ 通りをそれぞれ選んで加算することは、 $2 ^ s$ 通りの部分集合について $2 ^ t$ をそれぞれ加算することに対応します。

例えば、6 戦目に関して、 $(2,4) (3,3) (5,1)$ というルールが存在するとします。 $b = {0,2,4,5}$ という集合に対して 8 通りのルールを加算することは、 ${0,2,4,5}, {0,4,5}, {0,2,4}, {0,4}$ という 4 通りの集合に 2 ずつ加算することに対応します。というのも、 $(3,3)$ のように、元々対応する勝敗になる組み合わせが偶数の場合はルールを追加するかどうかは影響しないので、単に 2 を掛ければいいことがわかります。 $(2,4) (5,1)$ のように、対応する勝敗が奇数の場合はルールを選ぶことでその組み合わせを偶数 (0) に変えることができます。これは各 bit について独立に行えるので、ありうるすべての部分集合が列挙されます。

また、これは各 $b$ について先に $2 ^ t$ を掛け算した後に、ルールが存在するような bit についてのみ高速ゼータ変換を適用することで高速に求まります。

    for(int a = 0; a < n; a++) {
        if(rule[a][i - a] exists) {
            for(b in B) {
                if(b & 1 << a) dp[b ^ 1 << a] += dp[b];
            }
        }
    }

ただし、B はありうる b の集合です。

正方形のグリッドを斜めに見ているので、考える必要のある長さは $1, 2 , 3 , \cdots , N, N-1 , \cdots, 1$ となっているため、全体での計算量は $O(1 * 2 ^ 1 + \cdots + N * 2 ^ N + (N - 1) * 2 ^ {N-1} + \cdots + 1 * 2 ^ 1) = O(N * 2 ^ N)$ となります。

のいみのいみのいみのいみ

新春TCB 2021 羽根つき　解説

問題

解法