// created on 23.04.18
A. Ascending Matrix
先不考虑 \(a_{R,C}=V\) 的限制，考虑原问题，我们要找到 \(k-1\) 条值域轮廓线（起点 \((n,0)\) 终点 \((0,m)\)），使相互不越过。将第 \(i\) 条向下、右平移 \(i-1\) 格，变成了路径不交问题，可以 LGV 引理处理。
考虑 \(a_{R,C}=V\) 的限制，其实是 \((R+V-2,C+V-2)\) 这个位置 可以放数，并且上侧折线数恰好 \(V-1\) 条。那么枚举这条 \(y=c-x\) 线上所有点（作为中转点），如果在上侧就多一个 \(x\)，最后某个起点到某个终点的方案是 \(a+bx\) 的形式。只要插值就可以了。
时间复杂度 \(O(k^2(n+m+k)+k^4)\) 。
提交记录：Submission #97792 - QOJ.ac 。
B. Bit Operation
相当于每次从相邻两数中，挑选删除一个数。
那么枚举最后留下来的数，然后左右两侧分别是子问题，方案数是容易计算的。
时间复杂度 \(O(n)\) 。
提交记录：Submission #97799 - QOJ.ac 。
C. Count Min Ratio
注意答案为：
用 \(\mathcal{B}_t(z)\) 提取系数（\(\mathcal{[z^n]\frac{B_t(z)^r}{1-t+tB_t^{-1}(z)}}={tn+r\choose n}\)）：
令 \(F(z)+1=\mathcal{B}_{d+1}(z)\)，那么 \(\mathcal{\frac{B_{d+1}(z)^{R-dB}}{((d+1)B_{d+1}^{-1}(z)-d)^2}}\) 等价于 \(\frac{(1+F(z))^{R-dB+2}}{(1-dF(z))^2}\) 。用另类拉格朗日反演提取系数：
代回去：
是自然数幂和。即 \(\sum\limits_{i=1}^{n}i^k=[\frac{x^k}{k!}]\frac{e^{x}-e^{(n+1)x}}{1-e^x}\) 即可。
时间复杂度 \(O(B\log B)\) 。
提交记录：Submission #97802 - QOJ.ac 。
D. Do Use FFT
求 \(\sum\limits_{1\leq i\leq n}\left(C_i\times \prod\limits_{1\leq j\leq k}(A_i+B_j)\right)\) 。考虑令 \(F_k(x)=\prod (x+B_j),G(x)=\sum \frac{C_i}{1-A_ix}\)，那么 \(ans_k=[x^0]F_k(\frac{1}{x})G(x)\) 。
先分治求出 \(G(x)\) 。然后考虑分治求 \(ans_k\) 。在分治 \(\mathbf{divide}(x,l,r)\) 过程中，记 \(G_{x,l,r}(x)\) 为已经得到的结果，那么 \(G_{x,l,r}(x)\) 的最高次不超过 \(x^{r-l+1}\) 。往左儿子只要丢到后续无用项，然后递归。往右儿子只要在考虑左儿子后，丢掉无用项，然后递归。考虑左儿子的就是减法卷积。
时间复杂度 \(O(n\log^2 n)\) 。
提交记录：Submission #97807 - QOJ.ac 。
E. Edge Subsets
考虑将点放在平面上，对于 \(i\) 放在 \((x,y)\) 满足 \(x=\lfloor\frac{i}{B}\rfloor,y=\frac{i}{A}\bmod B\)（我们认为 \(\gcd(A,B)=1\)，显然可以分组做）那么每次转移，如果走 \(B\) 的边就是横着走，如果走 \(A\) 的边要么走到下一行，要么走到斜下方。
于是有两种做法：第一种是竖着扫，记录轮廓线，状态数 \(2^{B}\)；第二种是横着扫，记录轮廓线以及首行状态（因为最后一行会转移到首行），状态数 \(2^{2\lfloor\frac{n}{B}\rfloor}\) 。两个匀一下做到状态数不超过 \(2^{\sqrt{2n}}\) 。
时间复杂度 \(O(n2^{\sqrt{2n}})\) 。
F. Find the LCA
考虑 \(x\) 子树内部的构成，我们要减去的是每个子树的平方和，这和 \(\prod a\) 是不联系的。于是求出 \(g_i\) 表示 \(i\) 个点的 \(\prod a\) 和，在乘上 \(x\) 连边的方案数（\(x=1\) 比较特别，单独考虑）。
然后令 \(f_i\) 表示 \(i\) 个点树的方案数，乘平方和。这个拆开 exp 就行了。
时间复杂度 \(O(n\log^2 n)\) 。
提交记录：Submission #98626 - QOJ.ac 。
G. Games
K-nim，那么维度最多是 \(7\)，每一维是 \([0,6]\) 。因为存在 \(\omega_{7}\)，插入一个数时在每一维 DFT 一下。最后得到的就是 FWT 之后的结果，只要求出每位 \(k\) 次方求和就行了。
时间复杂度 \(O(b^b\log p+nb^{b+1})\)，\(b=7\)。
提交记录：Submission #98628 - QOJ.ac 。
H. Harsh Comments
根据期望线性性算每个 \(B_i\) 的答案。要求 \(B_i\) 在所有 \(A_i\) 后的概率，可以直接容斥。
时间复杂度 \(O((n+m)\sum a)\) 。
I. Inverse Problem
签到题就不做了。
J. Japanese Knowledge
我们构造新问题与原问题等价：
- 给定一个栈，按照值域扫描线，每次 Push 。遇见某个 \(A_i\) 可以 Pop 任意个数，如果此时栈空了，则称这次 Pop 是优秀的。
- 可以发现最后恰好 \(k\) 次优秀 Pop 对应了原问题 \(k\) 个 \(x_i=A_i\) 的答案：将 Push 看成使 \(A_i-x_i\) 加一即可。
考虑将问题反过来：
- 给定一个栈，按照值域扫描线，遇见某个 \(A_i\) 就 Push 。每次 Pop 任意个数。
- 可以发现最后栈中恰好剩下 \(k\) 个数的方案数，对应了原问题 \(k\) 个 \(x_i=A_i\) 的答案：每次值域往下扫，就是将已经离栈的元素集体减一，并决定一些元素脱离上界。
exactly 太强了，改成 at least：因为反向问题中，最后一个肯定是 Pop 。不妨将最后一步去掉，算 \(\geq k\) 个元素的方案数。这个和 \(\forall i\in[k+1, n],x_i< A_i\) 的所有合法方案一一对应：我们无非就是去掉了原先的最后 \(k\) 个 Push 。因为任意方案满足栈大小 \(\geq 0\)，所以加回 \(k\) 个 Push 保证了栈大小 \(\geq k\) 。
于是问题得到转化。剩下的问题考虑分治解决：看成一个表格，那么要统计的是底下的线上每个点，到右侧线上的路径数。我们考虑按照 \(A_{mid}\) 分成三个部分，递归时给每个右侧线上点带一个系数（继续往后走的方案数）。
那么先递归右上侧，求答案。中间的部分通过卷积求出左侧线和底下的线的答案，系数是组合数。然后拿中间部分求出的左侧线答案，去递归左下侧即可。
时间复杂度 \(O(n\log^2 n)\) 。