[1] 良い数列の必要十分条件

\(X\) が良い数列であることの必要十分条件は、以下で表されます。

• \(S\coloneqq \sum_{i=1}^N X_i\) は偶数
• 任意の \(i\ (1\leq i \leq N)\) にたいし、\(X_i+X_{i+1}\leq \frac{S}{2}\)

ただし、 \(X_{N+1}\) は \(X_1\) とします。

このことを証明しましょう。

必要性は簡単です。 グラフの次数の総和は必ず偶数になるので、\(S\) は偶数でなくてはなりません。また、\(X_i+X_{i+1}>\frac{S}{2}\) なる \(i\) が存在するとき、辺が \(X_i+X_{i+1}\) 本以上存在する必要があり、条件に反します。

十分性を示します。

補助的に \(B_i = \frac{S}{2} -(X_i + X_{i+1})\) で定義される変数を導入します。また、隣接しない \(u,v\) を選び \(X_u,X_v\) を \(-1\) することを、以下では操作と呼びます。すると、全ての \(B_i\) を非負に保つ操作が常に存在することが言えればよいです。

まず、操作をするとどのように \(B\) が変化するか考えます。\(u,v\) に操作をすると、\(B_{u-1},B_u,B_{v-1},B_v\) が \(+1\) されたのち、全ての \(B\) の要素が \(-1\) されます。

\(\mathrm{min}B\) が \(1\) 以上のときは適当に操作してよいです。

\(\mathrm{min}B=0\) を考えます。基本的には、\(B_i=0\) なる \(i\) であって、\(i\) と \(i+2\) に操作、または \(i-1\) と \(i+1\) に操作が可能なものにたいしその操作を行えばよいです。

そのような操作が存在しない場合を考えます。そのとき、\(X_i,X_{i+1}\) はほかの任意の要素とペアで操作をすることができます。よってこの場合も問題ないことが言えます。

---

[2] 包除原理の適用

任意の \(i\) についてという条件は考えづらいので、包除原理を用います。このとき、重要な考察として、条件に違反する \(i\) は高々 \(2\) 通りです。さらに、そのような \(i\) は隣接しています。なぜならば、要素を共有しない二つの箇所で条件に反する場合、総和が \(S\) を超えるからです。

以下の数え上げでは、形式的冪級数を用います。\(f(x)=1+x+\ldots+x^M = \frac{1-x^{M+1}}{1-x}\) とします。また、\([x^k]f(x)\) で \(f(x)\) の \(k\) 次の係数を表すこととします。

[2-1] 全体の個数

全体の個数は \(i\) が \(0\) から \(K\) の偶数を動くときの\( [x^i] f^N(x)\) の総和です。

これを求める方法を考えます。求める値は、 \([x^K] \frac{f^N(x)}{1-x^2}\) と一致しています。

\(g(x)=\frac{(1-x^{M+1})^N}{1-x^2}\) として、\(g\) をはじめに求めます。分子を二項定理で展開し、\((1-x^2)\) による除算は分母が疎なことを利用すると \(\mathrm{O}(N+K)\) で行えます。

次に、\([x^K]g(x)(1-x)^{-N}\) を求めます。\((1-x)^{-N}\) の係数列は負の二項定理を用いて \(\mathrm{O}(N+K)\) で求められることから、全体の個数を \(\mathrm{O}(N+K)\) で求めることができます。

[2-2] 違反箇所を一つ固定したときの数列の個数の総和

まず、違反箇所を一つ固定したときの数列の個数の総和を数えます。\(i=1\) で違反している数列の個数を数えあげ、最後に \(i\) の任意性から \(N\) 倍します。

総和 \(S\) と、\(t\coloneqq X_1+X_{2}\) を決め打ちます。このとき、\(S\) の範囲としては \(4M\) 未満のみ考えればよいことに注意してください。

\((X_1,X_{2})\) としてあり得るものの個数は \(O(1)\) で求められます。

残りの \(X_3,\ldots,X_N\) としてありうるものの個数は、\([x^{S-t}]f^{N-2}\) です。

上記の値を \(\mathrm{O}(1)\) で求めるためには、\(f^{N-2}\) の先頭 \(4M+1\) 項を求めておけばよいです。これは \(\mathrm{O}(M\log M),\mathrm{O}(M^2)\) などでできます。

以上より、違反箇所を一つ固定したときの数列の個数の総和を \(\mathrm{O}(M^2)\) で数え上げられました。

[2-3] 違反箇所を二つ固定したときの数列の個数の総和

次に、違反箇所を二つ固定したときの数列の個数の総和を数えます。この場合も、\(i=1,2\) で違反している数列の個数を数えあげ、最後に \(N\) 倍します。

総和 \(S\) を固定し、次に \(u\coloneqq X_1+X_{2}+X_{3}\) を全探索します。

\(S\) の固定のもとで、\(X_1 + X_2 > \frac{S}{2}, X_2+X_3 > \frac{S}{2}, X_1+X_2 + X_3 = u\) を満たす \((X_1,X_2,X_3)\) の組を全ての \(u\) について求めることが目標です。

\(X_2\) を全探索します。\(X_2=v\) とすると、条件を満たす\((X_1,v,X_3)\) の組の個数は \(l= \mathrm{max}(S/2-1-v, 0)\) として、\(l>m\) のとき \(0\) 、そうでないとき \(x^v(x^l+x^{l+1}+\ldots+x^m)^2\) と求まります。

これを毎回愚直に足すと、\(\mathrm{O}(M^2)\) となってしまいます。しかし、\(x^v(x^l+x^{l+1}+\ldots+x^m)^2=\frac{x^v(x^l-x^{m+1})^2}{(1-x)^2}\) と変形すると、分母が共通していることから分子だけ先に計算し、最後に除算をすることができます。この工夫により、計算量が \(\mathrm{O}(M)\) に落ちます。

残りについては、先ほどと同様です。結局こちらも \(\mathrm{O}(M^2)\) で数えられました。

[2-1]-[2-3] により、この問題を \(\mathrm{O}(M^2+K+N)\) で解くことができました。