Codeforces FFT标签题集 - Click Here
CF1342E
Difficulty 2300Solutions
显然棋子的分布是每行一个或每列一个，而这两个是对称问题，可以只考虑每行一个的情况最后再乘2。
对于每行一个的情况，能够产生attack的情况一定是某些列中存在了多余一个的棋子。设每一列从左到右看的棋子数量分别是$a_1,a_2,\cdots,a_t$，假设仅考虑棋子数不为零的列，即对于所有$a_i$有$a_i>0$。
那么$a_i$应该满足$\sum_{i=1}^t a_i=n, \sum_{i=1}^t (a_i-1)=k$。由两个式子我们能够确定$t=n-k$，换言之$a_i$的数量是恒定的，那么问题就转换成了这$t$个数字的所有填补方案对答案的贡献。对于一组方案$a_1,a_2,\cdots a_t$，其对答案贡献为$\frac{n!}{\prod a_i} \binom{n}{t}$。
显然可以生成函数优化这个式子，我们构造生成函数$\sum_{i>0} \frac{x^i}{i!}=e^x-1$，那么答案即为$\binom{n}{t} [x^n] (e^x-1)^t$，二项式展开计算即可。
CODE
CF1342E - Click Here
CF1542E2
Difficulty 2700Solutions
首先考虑满足字典序关系，其一定为某个长度为$i$的前缀相同，而后$p_{i+1} < q_{i+1}$。同时如果我们去掉这个长度为$i$的前缀后，剩余元素仍然能映射成一个长度为$n-i$的排列。
假设$p_{i+1}$和$q_{i+1}$映射后的位置分别为$p’_{i+1}$和$q’_{i+1}$，那么它们本身会产生$p’_{i+1}-1$和$q’_{i+1}-1$的逆序对数。换言之，我们需要在剩下$n-i-1$的后缀内任意填写，且满足逆序对差大于$q’_{i+1}-p’_{i+1}$。
这是个经典问题。我们考虑从小到大往序列内添加元素，此时产生的逆序对和位置相关。我们设$f(i,j)$表示已经放入前$i$小的元素，且逆序对差为$j$的方案数。此时枚举第$i$大的元素的摆放位置，能得到
传统转移是$O(n^4)$，如果我们将数组差分一下后，能够在$O(n^3)$内解决。而枚举$p_{i+1}$和$q_{i+1}$也是$O(n^3)$，因此总复杂度为$O(n^3)$。
CODE
CF1542E2 - Click Here
CF1548C
Difficulty 2500Solutions
对于每个询问$x_i$，其答案显然为$\sum_{k=0}^n \dbinom{3k}{x_i}$，因此问题转换为如何快速计算这个和式。
考虑如何快速计算。注意到$\sum_{k=0}^{3n} \dbinom{k}{x_i}$，我们是能快速计算得到的。其方法为添加一项$\dbinom{0}{x_i+1}$，此时能够两两合并，从而变成$\dbinom{3n+1}{x_i+1}$。
因此我们使用类似的方法处理该和式。我们设$f(i,j)=\sum_{3k+j \leq n} \dbinom{3k+j}{i}$，那么显然有
该方程显然是满秩的，能够通过$f(i-1,j)$快速计算$f(i,j)$，直接解方程即可。
CODE
CF1548C - Click Here