[1] The necessary and sufficient conditions for a good sequence

\(X\) is a good sequence if and only if both of the following hold:

• \(S\coloneqq \sum_{i=1}^N X_i\) is even.
• \(X_i+X_{i+1}\leq \frac{S}{2}\) for any \(i\ (1\leq i \leq N)\).

Here, regard \(X_{N+1}\) as \(X_1\).

Let us prove this.

The necessity is simple. The sum of the degrees in a graph is always even, so \(S\) must be even. Additionally, if there is \(i\) such that \(X_i+X_{i+1}>\frac{S}{2}\), there must be at least \(X_i+X_{i+1}\) edges, violating the condition for a good sequence.

Let us show the sufficiency.

We introduce auxiliary variables \(B_i = \frac{S}{2} -(X_i + X_{i+1})\). Additionally, let us define the following operation: choose \(u\) and \(v\) that are not adjacent, and decrease \(X_u\) and \(X_v\) by \(1\). Then, our objective is to show that one can always perform the operation so that all \(B_i\) stay non-negative.

Let us first consider how the operation affects \(B\). When the operation is performed on \(u\) and \(v\), each of \(B_{u-1},B_u,B_{v-1},B_v\) increases by \(1\), and then every element of \(B\) decreases by \(1\).

If \(\mathrm{min}B\) is \(1\) or greater, the operation may be performed arbitrarily.

Consider the case \(\mathrm{min}B=0\). Basically, one should choose \(i\) such that \(B_i=0\) and perform the operation on \(i\) and \(i+2\) or \(i-1\) and \(i+1\) where it is possible.

If this is impossible, one can pair each of \(X_i\) and \(X_{i+1}\) with any other element to perform the operation, so our claim holds.

---

[2] Applying the principle of inclusion-exclusion

The condition “\(X_i+X_{i+1}\leq \frac{S}{2}\) for any \(i\)” is difficult to handle, so let us use the principle of inclusion-exclusion. Here, it is important to observe that this condition is violated by at most two indices \(i\). Additionally, such \(i\)’s are adjacent, because if the condition were violated by two indices that are not adjacent, the sum would exceed \(S\).

In the counting below, we use formal power series. Let \(f(x)=1+x+\ldots+x^M = \frac{1-x^{M+1}}{1-x}\).

[2-1] The total number of sequences

This number is the sum of \( [x^i] f^N(x)\) over all even numbers from \(0\) to \(K\).

Let us try to find this. The sought value is equal to \([x^k] \frac{f^N(x)}{1-x^2}\).

Let \(g(x)=\frac{(1-x^{M+1})^N}{1-x^2}\) and find \(g\) first. This can be done in \(\mathrm{O}(N+K)\) time by expanding the numerator using binomial theorem and dividing it by \((1-x^2)\) using the fact that the denominator is “sparse”.

Next, let us find \([x^k]g(x)(1-x)^{-N}\). The sequence of coefficients in \((1-x)^{-N}\) can be found in \(\mathrm{O}(N+K)\) time using negative binomial theorem, so the total number of sequences can be found in \(\mathrm{O}(N+K)\) time.

[2-2] The case with one fixed position of violation

Let us find the sum of the numbers of sequences when the condition must be violated at one fixed position. We will find the count for \(i=1\) and then multiply it by \(N\) using the arbitrariness of \(i\).

Let us fix the sum \(S\) and \(t\coloneqq X_1+X_{2}\). Note that we only have to consider the values of \(S\) less than \(4M\).

For \((X_1,X_{2})\), the number of possible pairs of values can be found in \(O(1)\) time.

For the remaining \(X_3,\ldots,X_N\), there are \([x^{S-t}]f^{N-2}\) possible combinations of values.

To find the above value in \(\mathrm{O}(1)\) time, find the first \(4M+1\) terms of \(f^{N-2}\) beforehand, which can be done in, say, \(\mathrm{O}(M\log M)\) or \(\mathrm{O}(M^2)\) time.

Thus, the sum of the numbers of sequences when the condition must be violated at one fixed position can be found in \(\mathrm{O}(M^2)\) time.

[2-3] The case with two fixed positions of violation

Next, let us find the sum of the numbers of sequences when the condition must be violated at two fixed positions. Again, we will find the count for \(i=1,2\) and then multiply it by \(N\).

Let us fix the sum \(S\) and then try all values for \(u\coloneqq X_1+X_{2}+X_{3}\).

We want to count the triples \((X_1,X_2,X_3)\) such that \(X_1 + X_2 > \frac{S}{2}, X_2+X_3 > \frac{S}{2}, X_1+X_2 + X_3 = u\) for every \(u\) under the fixed \(S\).

Let us try all \(X_2\). Assume \(X_2=v\) and let \(l= \mathrm{max}(S/2-1-v, 0)\), then the number of sought triples \((X_1,v,X_3)\) is \(0\) if \(l>m\) and \(x^v(x^l+x^{l+1}+\ldots+x^m)^2\) otherwise.

If we naively add this every time, it will take \(\mathrm{O}(M^2)\) time. However, if we transform the formula as \(x^v(x^l+x^{l+1}+\ldots+x^m)^2=\frac{x^v(x^l-x^{m+1})^2}{(1-x)^2}\), the common denominator enables us to compute the numerator first, and then do the division in the end. With this improvement, the complexity is now \(\mathrm{O}(M)\).

The rest is the same as the earlier case. Again, the sum can be found in \(\mathrm{O}(M^2)\).

[2-1] through [2-3] solve the problem in \(\mathrm{O}(M^2+K+N)\) time.