总结
今天暴力打的还可以，但除了暴力全挂了。
t1 方法一数位 dp 还是不够熟悉；方法二容斥，虽然想题的时候有往容斥的方面思考，但是只差一步的时候放弃了。
t2 \(a+b<c\) 的 trick 第一次见，想清楚之后就很好写。
t3 高维前缀和，反复学反复忘的东西。
t4 败笔，冲了 2.5h 没写出来，tarjan + 点分治不够熟练。改题时发现是点分治挂了。
Solution
math
设 \(f_{i,S,0/1}\) 表示从高到低考虑了前 \(i\) 位，使用了 \(S\) 中的数码，且当前是否顶满 \(n\) 上街的方案数。时间复杂度为 \(\mathcal O(2^AAn)\)，其中 \(A=10\)，有 70 分。
考虑如果在第 \(i\) 位第一次不顶上街，那么枚举第 \(i\) 位的数码，设第 \(1\sim i\) 位的数码集合为 \(S_1\)，则第 \(i+1\sim n\) 位使用费的数码集合 \(S_2\) 应满足 \(\left\lvert S_1\cup S_2\right\rvert=A\)。
因此问题转化位任意填后 \(n-i\) 位，使用的数码是 \(0\sim 9\)，但要求恰好使用 \(A-\lvert S_1\rvert\) 个 \(S_1\) 以外的数码。
容易得到 dp 为令 \(g_{i,j}\) 表示填 \(i\) 个数码，有 \(j\) 个不同数码的方案数，用 \(g\) 在统计时拼一下答案即可。时间复杂度为 \(\mathcal O(nA)\)。
triangle
先考虑暴力，对于每次询问 \(l,r\)，先将序列 \([l,r]\) sort 一遍，不难发现每次选三个相邻的数最容易满足条件，于是从大到小扫一遍即可。时间复杂度为 \(\mathcal O(qn\log n)\)。
对于 subtask 4，因为数列的值只为 \(2^k\)，所以合法的为三个值相等，每次询问枚举长度 \(2^k\)，查询区间内有多少个这个数即可。
对于 subtask 5，不带修。考虑莫队，每添加一个数判断它在序列中的贡献，若其下标为 \(x\)，有贡献的点仅在 \(x-2,x-1,x,x+1,x+2\) 中。暴力判断即可。
对于正解，仍然考虑区间排序后得到的长度序列 \(b\)。
若 \(i,i+1,i+2\) 不能组成三角形，则有 \(b_i+b_{i+1}\leq b_{i+2}\)。
以此类推有 \(b_{i-1}+b_i\leq b_{i+1}\) 等。不难发现 \(b\) 序列的增长速度是与斐波那契数列近似的，实测为 \(c=43\) 次后 \(b\) 就不能变得再小了。所以一定能在前 \(\mathcal O(c)\) 大元素里面找到答案。使用线段树维护区间前 \(c\) 大即可。
时间复杂度为 \(\mathcal O(qc\log n)\)。
set
subtask 1,2 暴力。
subtask 3 对于单个 \(\lvert T\rvert\geq k\) 可以用组合数算出 \(\left\lvert S_i\cap T\right\rvert\geq k\) 的 \(i\) 的个数为 \(\sum_{i=\lvert T\rvert}^n\binom{n-\lvert T\rvert}{i-\lvert T\rvert}\)。
subtask 4 考虑每个 \(i\) 的贡献。设 \(F_i(T)=\left[\left\lvert S_i\cap T\right\rvert\geq k\right]\)，则 \(f(T)=\sum F_i(T)\)。只需要求出 \(F_i(T)=[S_i\subseteq T]\)，那么以 \(S_i\) 为下表的桶做高维前缀和得到 \(F_i\)，将这些桶加起来一起做高维前缀和就可以得到 \(f\)。
对于正解，若想求出 \(F_i\)，不妨对其做 FMT 得到 \(f_i\)，然后再高维前缀和回来得到 \(F_i\)。
也就是要找到一个 \(f_i\) 满足
\[\sum_{X\subseteq T}f_i(X)=F_i(T) \]设 \(\left\lvert S_i\cap T\right\rvert=l,l\geq k\)，那么 \(X\) 中有 \(\binom lj\) 个大小为 \(j\) 的 \(S_i\) 的子集。
若能找到容斥系数 \(a\) 满足 \(\sum_{i=k}^la_i\binom li=1\)，那么将 \(X\subseteq S_i\and \lvert X\rvert \geq k\) 的 \(f_i(X)\) 设置为 \(a_{\lvert X\rvert}\)，其余设置为 \(0\)，就能满足 \(f_i\) 的定义。
若要求 \(a\)，只需要按照定义 \(\mathcal O(n^2)\) 地推一下，即
\[a_l=\left\{ \begin{aligned} &1&(l=k)\\ &1-\sum_{i=k}^{l-1}a_i\binom li&(k<l\leq n) \\ & 0&(l<k) \end{aligned} \right. \]得到了 \(f_i\) 的计算式，令 \(h=f_1+f_2+\cdots+f_m\)，对 \(h\) 做高维前缀和能得到 \(f\)。
此时发现
\[h(X)=a_{\lvert X\rvert}\times\sum_{i=1}^m[x\subseteq S_i] \]于是先做一次 \(S_i\) 桶的超集和得到后面的因子，再分别乘上 \(\lvert X\rvert\) 即为 \(h\)。时间复杂度为 \(\mathcal O(m+2^n)\)。
graph
先考虑树的情况。显然是沿着树上的简单路径来回走一次，代价是路径边权和。则问题转化为 \(dis(u,v)\leq k\) 的 \((u,v)\) 对数，点分治即可。
具体地，对于分治的每个阶段，把每个子节点到当前子树重心的距离排序，用双指针来求小于等于 \(k\) 的边的数量，再用容斥思想减去在同一子树中的情况，把经过了从重心到新遍历的点的边两次的路径剪掉，最后统计答案即可。
对于一般情况，对每一个边双缩点，建立一个边双树再跑点分治就行了，还要乘上每个边的贡献，为两个边双点集大小的积。时间复杂度为 \(\mathcal O(m+n\log n)\)。
标签：rvert,复杂度,7.20,lvert,数码,mathcal,sum,模拟 From： https://www.cnblogs.com/QcpyWcpyQ/p/18313846