题解：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，所以有：
\begin{aligned}
B
&=\sum\limits_{j=0}^{m}(-1)^j\binom{j}{k}\\
&=[x^k]\sum\limits_{j=0}^{m}(-1)^j(1+x)^j\\
&=[x^k]\sum\limits_{j=0}^{m}(-(1+x))^j\\
&=[x^k]\sum\limits_{j=0}^{m}\frac{1-(-(1+x))^{m+1}}{1-(-(1+x))}
\end{aligned}
其中最后一步是等比数列求和。
化简一下分母：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}。
第一部分：
\begin{aligned}
\frac{1}{2+x}
&=\frac{1}{2}\times\frac{1}{1+\frac{x}{2}}\\
&=\frac{1}{2}\times \sum\limits_{s\geq 0}(-1)^s \left(\frac{x}{2}\right)^s\\
&=\sum\limits_{s\geq 0}(-1)^s 2^{-s-1} x^s
\end{aligned}
所以 [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 卷到一起。
\begin{aligned}
\left[x^k\right]\frac{(1+x)^{m+1}}{2+x}
&=\sum\limits_{t=0}^k\binom{m+1}{t}\times [x^{k-t}]\frac{1}{2+x}\\
&=\sum\limits_{t=0}^k\binom{m+1}{t}\times (-1)^{k-t} 2^{-(k-t+1)}
\end{aligned}
所以这个式子最后就是：
\begin{aligned}
&(-1)^{m+1}\sum\limits_{t=0}^k\binom{m+1}{t}\times (-1)^{k-t} 2^{-(k-t+1)}\\
=&(-1)^{m+1}(-1)^{k}\frac{1}{2^{k+1}}\sum\limits_{t=0}^k\binom{m+1}{t}\times (-1)^{t}2^{t}\\
=&(-1)^{m+1}(-1)^{k}\frac{1}{2^{k+1}}\sum\limits_{t=0}^k\binom{m+1}{t}\times (-2)^{t}\\
\end{aligned}
然后考虑怎么求：
\sum\limits_{t=0}^k\binom{m+1}{t}\times (-2)^{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)。