フレンズは \(a_i\) の昇順にソートしておく.

\(i\) 番目のフレンズを通る経路の集合を \(A_i\) とすると, フレンズ \(K = \{ k_1, k_2, \dots, k_{ \abs{K} } \}\) のどれも通らない経路の数は

\[\abs{ \overline{ A_{k_1} \cup A_{k_2} \cup \cdots \cup A_{ k_{ \abs{K} } } } }\]

であり, これは包除の定理を用いて

\[\sum_{I \subseteq K} (-1)^{ \abs{I} } \abs{ A_{I_1} \cap A_{I_2} \cap \cdots A_{ I_{ \abs{I} } } }\]

となる. フレンズはソートされているので \(\sum\) の中身は組み合わせの数を用いてあらかじめ計算しておくことができる.

これをすべての \(K\) について計算するのだが, そのまま計算すると \(O(K \cdot 2^K + 4^K)\) となり, 部分集合を列挙する部分を工夫すれば \(O(k \cdot 2^K + 3^K)\) に落とせるが, まだ間に合わない.

しかし, この式は部分集合の総和を求めているので高速ゼータ変換が使え, \(O(K \cdot 2^K)\) に抑えることができる.

実際の計算量は組み合わせの計算部分も必要である.