简要题意
给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式：
- 长度不同时，长度短的排在低次位。
- 长度相同时，按字典序排序。
简单而言，长度是第一关键字，字典序是第二关键字。现在给定 \(Q\) 个询问，每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。
数据范围
\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)
Continue reading →给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式：
简单而言，长度是第一关键字，字典序是第二关键字。现在给定 \(Q\) 个询问，每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。
\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)
Continue reading →首先看到这个题可以考虑树套树，然后就做完了。
我们考虑用二维树状数组进行差分。当然，如果按正常的想法差分的话，我们只能想到用前缀和维护单点值，而不是维护区间异或和。我们设差分后的结果：
\[ d_{i, j} = a_{i, j} \oplus a_{i – 1, j} \oplus a_{i, j – 1} \oplus a_{i – 1, j – 1} \]
Continue reading →算是个简单题吧。
首先列个暴力式子：
\[ \sum_G \sum_{i = 1}^n d_i^k \]
发现很不现实。我们考虑把点拆开来考虑，因为全集里面可以直接独立的来算。考虑某个点度数为 \(x\) 的方案数，就变成了：
\[ n \sum_{x = 0}^{n – 1} x^k f(x) \]
其中 \(f(x)\) 代表的是一个图某个点的度数为 \(x\) 的方案数。其实稍微思考下就知道，我们可以把这个点剥离出来，强制连边之后再生成一个图即可：
\[ \begin{aligned} f(x) &= {n – 1 \choose x} 2^{n – 1 \choose 2} \\ ans &= n \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} 2^{n – 1 \choose 2} \\ &= n2^{n – 1 \choose 2} \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} \end{aligned} \]
首先，如果没有限制的话，其实从叶子结点来抽是一定有解的，可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边，初步思考可以把每个点都作为最后一个节点，然后来看新的图有没有环，这样是 \(\Theta(n^2)\)。
这道题很有意思。首先搞一个 \(DP\) 来算出不同长度的不降子序列的个数，方程为：
\[ f[i, j] = \sum_{k < i, a_k \leq a_i} f[k, j – 1] \]
发现可以用树状数组优化，所以这里的复杂度为\(O(n^2 \log n)\)。设\(g[i] = \sum_{i = 1} f[i, n]\)，考虑对答案的贡献。对于一个\(i\)，有\(g[i] * (n – i)!\)种方案做变换，但是考虑这\((n – i)!\)中包含了提前变换完成的可能，也就是在我们从合法序列中删去了合法元素的可能，这样肯定是不行的。考虑进行容斥，贡献就是\(g[i](n-i)! – g[i+1](n – i – 1)!(i + 1)\)，表示在这些里选择\(i+1\)个合法元素的方案。
这道题很有意思啊。如果暴力枚举，答案式子：
\[ans = \sum_{x}^n \sum_{y}^m {up_{x,y} \choose k} {left_{x,y} \choose k} {right_{x,y} \choose k} {down_{x,y} \choose k}\]
其中\(up, left, right, down\)代表上下左右的常青树棵树。如何降低复杂度？
首先，我们可以考虑进行离散化：上下左右只要有为\(0\)的情况是不可能对答案有贡献的。然后，发现空隙中上下的部分：