AGC001E 的无组合意义的纯净做法
LCuter
·
·
题解
组合意义没有精神！！我们代数解法才是你们的老大哥！！
题目等价于求：
\sum_{i=1}^{n}\sum_{j=1}^n\binom{t_i+t_j}{a_i+a_j}
其中 t_i=a_i+b_i。
我们希望将 i 与 j 拆开，那么只需利用范德蒙德卷积：
\begin{aligned}
\sum_{i=1}^{n}\sum_{j=1}^n\sum_{k}\binom{t_i}{a_i-k}\binom{t_j}{a_j+k}
\end{aligned}
显然可以交换求和次序，然后记
F(k)=\sum_{i=1}^n\binom{t_i}{a_i+k}
则原式化为：
\sum_{k}F(k)F(-k)
问题转为求解 F(k)。
直接计算是 O(nk) 的，略去不提。
考察数列：
T_i(k)=\binom{t_i}{a_i+k},k\in[-a_i,b_i]
不妨将 T_i(k) 看作二维平面的一个点 (t_i,a_i+k)，该点会给 F(k) 贡献 T_i(k)，容易发现 T_i 构成了垂直 x 轴于 (t_i,0) 且高为 t_i 的线段。
观察 x=x_0 上的线段，它们的高度是一致的，只是贡献区间平移了（这取决于 a 的值）。
现在问题转化为，有一个初始全为 0 的模板序列，q 次修改，第 i 次修改给出一个修改序列和一个区间 [l_i,r_i]，要求把修改序列合并到模板序列的对应区间上，最后求模板序列。
当然，修改序列还有个特点，它是：
\binom{t_i}{0},\binom{t_i}{1},\cdots,\binom{t_i}{t_i}
那么我们将这些东西看作是对 OGF 的修改，再次进行转化。
首先让原来的这个东西整体向右平移一定单位 S，现在下标一定是非负的。
对于一个修改序列，我们发现它的 OGF 就是 (1+x)^{t_i}。那么我们要让它平移整体平移量与自身平移量，也就是 S-a_i。
\sum_{i=1}^nx^{S-a_i}(1+x)^{t_i}
为了方便，我们将问题转为计算：
A(x)=\sum_{i=1}^{n}x^{p_i}(1+x)^{q_i}
或者说是计算：
\begin{aligned}
A(x)=\sum_{i=1}^m(1+x)^iQ_i(x)
\end{aligned}
使用秦九韶算法即可 O(n+m^2) 解决，值得一提的是，我乱实现的屑代码目前领先其它所有洛谷提交。