[yukicoder] No.1594 Three Classes

概要

問題文 → ■
公式解説 → ■
自分の提出 → ■

想定されている解法よりもだいぶ難易度が高いですが、$O(N^22^N)$ で解けます。$N \leq 12$ の制約では特に高速にならないですが、この解法であれば $N=20$ 程度まで解くことができます。

解法

subset convolution を利用できます。

参考：https://judge.yosupo.jp/problem/subset_convolution

今回は、総和/3 に等しい集合に 1、他の集合に 0 を対応させた関数を、subset convolution に関して $3$ 乗すればよいです。

ranked zeta をしたあと、各点で多項式の $3$ 乗を計算し、包除原理で答を求めればよいです。