問題
解法
包除原理により数える。
$0\leq i \leq A+B+C-3$ に対して条件 $P _ i$ を「$S _ iS _ {i + 1}S _ {i + 2}$ で条件に違反する」と定める。$X\subseteq \lbrace 0,1,\ldots, A+B+C-3\rbrace$ に対して、全ての $i\in X$ で $P _ i$ を満たすような $S$ の個数を $n(X)$ とする。このとき答えは以下で表される。
$$\sum _ {X\subseteq \lbrace 0,1,\ldots, A+B+C-3\rbrace} (-1) ^ {\lvert X\rvert} n(X).$$
$X$ の要素 $i, j$ が $\lvert j - i\rvert \lt 3$ を満たす場合、$S _ i$ と $S _ j$ を独立に決めることは出来ず、$S _ i$ の値から $S _ j$ の値が一意に定まる。
$S _ i$ の値から $S _ j$ の値が一意に定まるならば辺 $\lbrace i, j \rbrace$ を張ったグラフの連結成分は区間を成す。そこで、この区間を単位として遷移する DP を考える。
長さ $i + 3$ の区間による遷移の係数を考えるために $F$ を以下で定める。$F$ の $2$ つめの添字は $X$ の要素数の偶奇を表す。
$$\begin{aligned} F _ {i, 0} &= \begin{cases} 0 & \text{if } i \lt 0 \\ 0 & \text{if } i = 0 \\ F _ {i - 2, 1} + F _ {i - 1, 1} & \text{if } i \gt 0 \\ \end{cases}, \\ F _ {i, 1} &= \begin{cases} 0 & \text{if } i \lt 0 \\ 1 & \text{if } i = 0 \\ F _ {i - 2, 0} + F _ {i - 1, 0} & \text{if } i \gt 0 \\ \end{cases}. \end{aligned} $$
$F _ {i, 0} - F _ {i, 1}$ を計算してみると、次が成り立つ。
$$ F _ {i, 0} - F _ {i, 1} = \begin{cases} -1 & \text{if } i \equiv 0 \pmod{3} \\ 1 & \text{if } i \equiv 1 \pmod{3} \\ 0 & \text{if } i \equiv 2 \pmod{3} \\ \end{cases}. $$
従って、DP を形式的冪級数で解釈すると求める答えは以下で表される。
$$\begin{aligned} & \lbrack x ^ A y ^ B z ^ C\rbrack \sum _ {k = 0} ^ \infty \left((x + y + z) + \sum _ {i = 1} ^ \infty (xyz) ^ i (x+y+z) + \sum _ {i = 1} ^ \infty -3(xyz) ^ i \right) ^ k \\ = & \lbrack x ^ A y ^ B z ^ C\rbrack \sum _ {k = 0} ^ \infty \left(\dfrac{x + y + z - 3xyz}{1 - xyz} \right) ^ k \\ = & \lbrack x ^ A y ^ B z ^ C\rbrack \dfrac{1}{1 - \dfrac{x + y + z - 3xyz}{1 - xyz}} \\ = & \lbrack x ^ A y ^ B z ^ C\rbrack \dfrac{1 - xyz}{1 - ( (x + y + z) - 2xyz)} \\ = & \lbrack x ^ A y ^ B z ^ C\rbrack \dfrac{1}{1 - ( (x + y + z) - 2xyz)} - \lbrack x ^ {A - 1} y ^ {B - 1} z ^ {C - 1}\rbrack \dfrac{1}{1 - ( (x + y + z) - 2xyz)}. \\ \end{aligned}$$
あとは $\lbrack x ^ p y ^ q z ^ r\rbrack \dfrac{1}{1 - ( (x + y + z) - 2xyz)}$ の計算ができればよいが、これは以下のように計算できる。
$$\begin{aligned} & \lbrack x ^ p y ^ q z ^ r\rbrack \dfrac{1}{1 - ( (x + y + z) - 2xyz)} \\ = & \lbrack x ^ p y ^ q z ^ r\rbrack \sum _ {k = 0} ^ \infty ( (x + y + z) - 2xyz) ^ k \\ = & \sum _ {k = 0} ^ \infty \binom{k}{t _ k} (-2) ^ {k - t _ k} \dfrac{t _ k !}{(p - k + t _ k)! (q - k + t _ k)! (r - k + t _ k)!} \quad (t _ k \coloneqq (3k - (p + q + r) ) / 2) \\ = & \sum _ {k = 0} ^ {p + q + r} \binom{k}{t _ k} (-2) ^ {k - t _ k} \dfrac{t _ k !}{(p - k + t _ k)! (q - k + t _ k)! (r - k + t _ k)!}. \end{aligned}$$
全体の計算量は $\Theta(A + B + C)$ 時間である。
