题解-AtCoder Regular Contest 133
被打烂了，啥也不会。
A - Erase by Value
先判掉一些全相等的平凡情况。然后考虑一个性质，如果不选第一个数或第一个与第一个数不同的数，那么选啥都一样。于是我们比较这两个数，如果后者小那么把第一个数选了即可。否则我们考虑递归到子问题，也就是把前一段全部一样的数删掉然后继续做。怎么证明？直觉。。。其实只用到一个性质 \(a
B - Dividing Subsequence
如果从新定义 \(=\) 为约数即可，可以转换为 LCS，又知排列的 LCS 可以转成 LIS，于是就做完了。复杂度 \(O(n\log^2n)\)。
C - Row Column Sums
可以证明如果有解则前 \(n-1\) 行 \(m-1\) 列瞎填都可行。所以不妨把这些位置全部填 \(k-1\)。然后对于边界的情况补成 \(k-1\) 即可，贪心证明这样不会更劣。
D - Range XOR
E - Cyclic Medians
F - Random Transition
加强对二元 GF 的理解。首先是概率统计里很不套路的一步转换，把一个数 \(x\) 想象成一恰有 \(x\) 个 \(1\) 的长度为 \(n\) 的 \(01\) 串。于是操作相当于等概率选择一个位置反转。想出这一步估计就够神仙了。既然如此我们只需考虑再经过了 \(K\) 轮后有几个 \(1\) 即可。注意我们并不关心一开始每个 \(1\) 在什么位置。
实际上我们想要知道从 \(a\) 个 \(1\) 变成 \(b\) 个 \(1\) 的方案数。这里需要考虑每个位置有多少轮是翻了那里，原先就是 \(1\) 的位置翻偶数次是 \(1\)，原先是 \(0\) 的位置翻奇数次是 \(1\)，所以我们要求即为 \(k^a(y\cdot \frac{e^x-e^{-x}}{2}+\frac{e^x+e^{-x}}{2})^{N-a}\)。设 \(P=(y+1)e^{x},Q=(y-1)e^{-x}\)。那么原来的生成函数可以写成 \(\frac{1}{2^N}(P+Q)^a(P-Q)^{N-a}\)，不管尝试，考虑求后面的部分。考虑所有的 \(a\)，列出最终的生成函数 \(\sum\limits_{a=0}^{N}A_a(P+Q)^a(P-Q)^{N-a}\)。把后面两项二项式定理展开，化一化可以转换成 \(\sum\limits_{i=0}^{N}w_iP^iQ^{N-i}\)。而 \(w_i\) 通过计算发现等于 \([z^i]\sum\limits_{i=0}^{N}A_i(z+1)^i(z-1)^{N-i}\)。而答案的生成函数也可以表示成 \(K!\sum\limits_{i=0}^{N}w_i(2i-N)^{K}(y+1)^{i}(y-1)^{N-i}\)。于是我们要解决的问题变成了：
给定一个序列 \(C\)，求 \(\sum\limits_{i=0}^{N}C_i(z+1)^i(z-1)^{N-i}\)。
这个问题显然可以分治NTT在 \(O(n\log^2n)\) 的时间解决，但其实可以通过换元（或者复合）在 \(O(n\log n)\) 的时间解决。
考虑求出 \(G(z)=\sum\limits_{i=0}^{N}C_iz^i(z-2)^{N-i}\)。这东西你把后面二项式定理展开一下就可以卷了。然后代入 \(z+1\) 就可以得到原式，即 \(\sum\limits_{i=0}^{N}g_i(z+1)^{i}\)。这玩意也可以二项式展开然后卷。