ARC160D
直接考虑从 \(A\) 变为全零数列不太好做，考虑将问题转化为从全零数列通过两种操作可以得到的 \(A\) 数列的个数。发现只要满足每个区间的加一次数 \(\le k\) 就能保证不同操作序列得到数列的唯一性，这个很好感性理解。
于是题目转化成统计序列 \(b_{1\sim 2n-k+1}\) 的个数，要求：
-
\(\sum\limits_{i=1}^{2n-k+1}b_i=\dfrac{m}{k}\)
-
\(\forall i\in[1,n-k+1],b_i<k\)
这是一个有上界的插板法，容斥，钦定 \(i\) 个元素不合法，其余任意，那我们得到：
\[\Large{ans=\sum\limits_{i=0}^{n-k+1}(-1)^i\dbinom{n-k+1}{i}\dbinom{\frac{m}{k}-ik+2n-k}{2n-k}} \]注意 \(m\) 很大所以无法用数组存组合数，直接暴力计算即可，时间复杂度 \(O(n^2\log mod)\)。
P7880 [Ynoi2006] rldcot
树上点对计数。对于每个点 \(x\) 考虑其作为 \(\text{lca}\) 贡献：当区间中包含 \(x\) 或是有一对点来自 \(x\) 的不同子树，设为 \((a,b)\)，钦定 \(a<b\)，但这样的点最多是 \(O(n^2)\) 的。可以发现对于点对 \((a,b),(c,d)\)，若 \(a\le c,d\le b\)，那么 \((a,b)\) 就是无用的，因为包含了 \((a,b)\) 就一定包含了 \((c,d)\)，也就是找区间内的支配对就行。通过 dus on tree 求出所有支配对共 \(O(n\log n)\) 对，再进行查询。
博客园就是好，直接把图片拖进编辑器里就好了，等我上大学了一定要支持。