题解：AT_tenka1_2019_f Banned X

首先显然我们 $0$ 无所谓，计算 $f(m)$ 表示只有 $m$ 个 $1/2$ 的方案数，然后加起来，$ans=\sum\limits_{m=0}^n \binom{n}{m}\times f(m)$。

考虑 $f(m)$ 怎么算。首先 $\sum\lt X-1$ 肯定是对的。这个我们可以先计算。设 $F(n,m)$ 表示 $n$ 个值域 $[1,2]$ 内的数和为 $m$ 的方案数，这个显然就是 $\binom{n}{m-n}$。枚举 $s\in[0,X-1)$，先把 $\sum F(m,s)$ 算到贡献里。

然后注意到，如果 $s\geq X-1$，则序列一定出现了 $X-1$ 这个前缀和。

因为你不可能出现 $X$，又不可能直接跳到 $X+1$（序列内值域为 $[1,2]$）。

然后我们枚举什么时候 $X-1$ 这个前缀和出现，设 $\sum\limits_{j=1}^i a_j=X-1$，则可以发现，$a_{i+1}=2$，因为填 $1$ 就出现 $X$ 了。而 $a_1=2$，因为如果填 $1$ 则 $[2,i+1]$ 就是 $X$ 了。

同理可以推出来 $j\in[1,m-i]$ 和 $j\in [i+1,m]$ 的 $a_j$ 都必须是 $2$。

若 $m-i\geq i+1$ 就是全填 $2$，可以直接判掉。如果 $2i\geq X-1$ 且 $X$ 是奇数，那么全填 $2$ 就合法。

若 $m-i\lt i+1$ 那么就是 $m-2\times(m-i)$ 个值域在 $[1,2]$ 的数，要求和为 $X-1-2 \times(m - i)$。就是 $F(m-2\times(m-i),X-1-2 \times(m - i))$。

然后 $\mathcal O(n^2)$ 就做完了。

考虑优化到 $\mathcal O(n)$。

首先前面的这个 $\sum F(m,s)$ 先展开成 $\sum\limits_{j=0}^{\min\{m,X-1-m-1\}}\binom{m}{j}$。

这个就是动态的下指标求和，参考这个题 https://atcoder.jp/contests/tenka1-2014-final/tasks/tenka1_2014_final_d，我们组合数移动一个指标的时候，是可以 $\mathcal O(1)$ 更新的。利用这个就可以直接把 $\sum F(m,s)$ 优化掉。

然后 $m-i\geq i+1$ 这个显然取到 $i=\lfloor (m-1)/2\rfloor$，这个可以直接判掉。

剩下的就是 $\sum\limits_{i=\lfloor (m-1)/2\rfloor+1}^{m} \binom{2\times i-m}{X-1-m}$。

这个是上指标求和但是隔一个求一个。

现在我们考虑怎么求这个。接下来的部分抄袭了 ChatGPT。

设 $k=X-1-m$，我们关心的是 $\sum\limits_{j=0\land j\equiv m\pmod 2}^{m}\binom{j}{k}$。

设 $S_{\text{odd}}=\sum\limits_{j\equiv 1\pmod{2}}\binom{j}{k},S_{\text{even}}=\sum\limits_{j\equiv 0\pmod{2}}\binom{j}{k}$。

设 $A=\sum\limits_{j=0}^{m}\binom{j}{k},B=\sum\limits_{j=0}^{m}(-1)^j\binom{j}{k}$。

则 $A=S_{\text{even}}+S_{\text{odd}},B=S_{\text{even}}-S_{\text{odd}}$。

所以 $ans=\frac{A+(-1)^{m}B}{2}$。

考虑 $A$ 怎么算。这个是上指标求和，曲棍球恒等式，$A=\binom{m+1}{k+1}$。

而 $B$，我们使用一些 GF 手法。

因为 $\binom{j}{k}=[x^k](1+x)^j$，所以有：

其中最后一步是等比数列求和。

化简一下分母：$B=[x^k]\sum\limits_{j=0}^{m}\frac{1-(-(1+x))^{m+1}}{2+x}$。

我们分成两部分：$B=[x^k]\sum\limits_{j=0}^{m}\frac{1}{2+x}-[x^k]\sum\limits_{j=0}^{m}\frac{(-(1+x))^{m+1}}{2+x}$。

第一部分：

所以 $[x^k]\sum\limits_{j=0}^{m}\frac{1}{2+x}=[x^k]\frac{1}{2+x}=(-1)^k 2^{-(k+1)}=(-1)^k \frac{1}{2^{k+1}}$。

第二部分：

首先 $(-(1+x))^{m+1}=(-1)^{m+1}(1+x)^{m+1}$。

然后你拿 $\frac{1}{2+x}$ 的形式幂级数和 $(1+x)^{m+1}=\sum\limits_{t=0}^{m+1}\binom{m+1}{t}x^t$ 卷到一起。

所以这个式子最后就是：

然后考虑怎么求：

这个。

这个是下指标求和带一个 $(-2)^t$。

类似于普通的动态下指标求和，这里改下指标也是可以 $\mathcal O(1)$ 的。然后上指标增加的转移是 $n\gets n+1,ans\gets 2 \times (-2)^k \times \binom{n}{k}-ans$。

好的，然后推完了，预处理阶乘、阶乘逆元、$2^k$，$2^{-k}$ 等即可做到 $\mathcal O(n)$。