「2021 CCPC 桂林」J – Suffix Automaton

简要题意

给定一个字符串 \(S\)。对该字符串本质不同的子串定义一种排序方式:

  • 长度不同时,长度短的排在低次位。
  • 长度相同时,按字典序排序。

简单而言,长度是第一关键字,字典序是第二关键字。现在给定 \(Q\) 个询问,每个询问要求找到在该排序下排名为 \(k\) 的子串的第一次出现位置。

数据范围

\(1 \leq |S|, Q \leq 10^6, 1 \leq k \leq 10^{12}\)

继续阅读“「2021 CCPC 桂林」J – Suffix Automaton”

BZOJ5093:[Lydsy1711月赛]图的价值 – 题解

主要思路

算是个简单题吧。

首先列个暴力式子:

\[ \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} \]

继续阅读“BZOJ5093:[Lydsy1711月赛]图的价值 – 题解”

BZOJ4361:isn 题解

解法

这道题很有意思。首先搞一个 \(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\)个合法元素的方案。

继续阅读“BZOJ4361:isn 题解”

P2154:[SDOI2009]虔诚的墓主人题解

解法

这道题很有意思啊。如果暴力枚举,答案式子:

\[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\)的情况是不可能对答案有贡献的。然后,发现空隙中上下的部分:

继续阅读“P2154:[SDOI2009]虔诚的墓主人题解”