小 w 的序列

好菜呀！！！！！！！！

Link

直接快进到，我有 \(q\) 次操作，每次可以flip \(n\) 个 bit 其中一个，问最后有 \(k\) 个正面的方案数。

\(q\le 10^{18},n,k\le 10^5\)

这个题直接推生成函数真的是 十分困难 我问sjw,zzy 都没有得到一个比较不那么“人类智慧”的方法。（但是当时Tiw 2h切了。。）

其实zzy当时提醒说，我又没有尝试去 \(1-x,1+x\) 配对，这其实也让我想起来好久以前学数学的时候，有的题这么凑起来十分简单。换元的重要性必须要注意注意注意！

---

生成函数

直接列出来：

\[ \begin{aligned} \forall k,&g(x)=(\frac{e^x+e^{-x}}{2})^k(\frac{e^x-e^{-x}}{2})^{n-k}\\ \end{aligned} \]

第一步的结果可谓是我真的不懂是怎么想出来的。

可以拿容斥解释，也可以拿一步很神秘的换元解释。

就是我们钦定 \(k\) 个偶数中 \(i\) 个数不选偶数的数，这样能得到如下式子。

\[ \begin{aligned} \sum_{i\le k}\binom{k}{i}(-1)^ke^{k-i}(\frac{e^x-e^{-x}}{2})^{n-i} \end{aligned} \]

剩下的也就是拆开括号了。其实下面的步骤，我也不能很好的一眼看出，总之就是要多注意一个 \(\sum\) 内是 \(A\) 和 \(B\) 进行某种二元运算，贡献到 \(C\) 这样的我们是可以卷积的。

为什么会这样的？我想，原因大抵是我们并不要算某一个“多项式”的值，而是变成了算许多个多项式的某一项值。

而这个和我们所熟悉的算“某一个多项式”的值差什么呢？

答案是：“转置”。

---

转置原理

转置原理说的是如果我们能在 \(T(n)\) 算出来 \(\mathbf Ma=b\) 那么我们也必定可以在 \(T(n)\) 算出来 \(\mathbf {M^{T}}b=a\)。

注意我们没有在求逆，而是转置。

那么这个题我们该如何看成转置问题呢？

对于“每一个k”，求出来 \([x^q](\frac{e^x+e^{-x}}{2})^k(\frac{e^x-e^{-x}}{2})^{n-k}\)。

看成关于 \(e^x\) 的多项式，这样变成一个有限多项式。

此时我们相当于让每一行都是一个多项式的系数的矩阵，去乘上一个固定的向量 \(e^{ix}\) 对 \([x^q]\) 贡献的向量。

那么现在问题是 \(\mathbf{M}a\) 的。我们考虑转置问题。

我们惊奇的发现，转置问题竟然真的变成了 求解一个多项式，当然，对于这样的问题我们是熟悉的。

现在相当于给定我们任意一个输入，需要我们输出 \(f(x)=\sum_{i} b_i(x-1)^i(x+1)^{n-i}\)。

这个并不困难毕竟对多项式运算是我们的主场。

首先进行换元（感觉也是很必要的） \(g(x)=f(x+1)=\sum_{i} x^i(x+2)^{n-i}\) 这样就可以拆括号卷积了。

我们得到了一个需要两次 FFT 的转置问题求解方法。

那么原问题也需要两次FFT。

考虑流程：

\[ \begin{aligned} g(x)=f(x+1)&=\sum_{i} b_ix^i(x+2)^{n-i}\\ &=\sum_{i}b_ix^i\sum_{j\le n-i} \binom{n-i}{j} x^j2^{n-i-j}\\ &=\sum_{i}x^i(n-i)!\sum_{j\le n-i}\frac{x^j}{j!} \frac{(n-i-j)!} 2^{n-i-j}\\ \end{aligned} \]

第一步是把这个多项式点乘上 \((n-i)!\)，然后乘上一个 \(e^x\)，最后再多项式平移。

我们注意到多项式平移的效果就是某个方向的二项式反演。

而另一个方向的二项式反演的效果是我们熟知的，点乘 \(\frac{1}{n!}\) 卷积 \(e^x\) 然后再点乘 \(n!\)。

那么现在我们得到了一个转置算法。

首先将输入的二项式反演。接下来减卷积 \(e^x\) 然后点乘 \(\frac{1}{(n-i)!}\)。