太阳神的宴会

from nealchen2003

比赛的时候有热心 djq_cpp 和 jiangly 告诉我，后缀数组改一下就能做了。不过我给的解是一个改造的后缀自动机，看上去更好写一点。

简明题意

$$ 设字符集 $\mathrm{\Sigma }$ 为前 $k$ 个小写英文字母的集合，题中所有字符串均由 $\mathrm{\Sigma }$ 中的字符构成。

对于 $\mathrm{\Sigma }$ 上的置换 $f$ 和 $s\in {\mathrm{\Sigma }}^{\ast }$，令 $s$ 作用 $f$ 后的结果为 $f(s)=f\left(s_1\right)f\left(s_2\right)\cdots f\left(s_{|s|}\right)$。

我们称字符串 $s$ 与字符串 $t$ 相似，当且仅当存在一个 $\mathrm{\Sigma }$ 上的置换 $f$，使得 $f(s)=t$，记作 $s\sim t$。例如，字符串aab与bba相似，与abb不相似。

现给出 $n$ 个字符串 $S_1,S_2,\dots ,S_n$. 记 $C_i$ 为全体与 $S_i$ 的至少一个子串相似的字符串的集合。

称字符串 $T$ 是好的，当且仅当存在字符串 $T_1,T_2,\dots ,T_n$，使得 $T_i\in C_i$，且 $T=T_1{T}_2\cdots T_n$。

求有多少个好的字符串。

初步分析

首先，$\sim$ 是一个等价关系，且若 $s\sim t$，则 $s[l,r]\sim t[l,r]$。

算法一

用于解决 $n=1$，$k=2$，$L\le 1000$ 的数据。

在 $k=2$ 的情形下，$\mathrm{\Sigma }$ 上只有两种置换，$S_1$ 只有 $O\left(L^2\right)$ 种子串。因此 $C_1$ 中所有可能出现的字符串可以直接枚举。考虑这些字符串的去重问题，容易想到用 Trie 来解决。

因此得出一个简单的算法：枚举 $\mathrm{\Sigma }$ 上的置换 $f$，将 $S_1$ 的所有后缀作用 $f$ 后插入 Trie。最终 Trie 的结点数即为所求。时空复杂度 $O\left(L^2\right)$，期望得分 $2$ 分。

形状序列

当 $k$ 更大时，枚举置换将带来巨大的时空复杂度。因此，我们要考虑一种更高效的方法来描述相似关系的等价类。

为了判定相似性，我们试图将字符串对应到一种辅助序列上，使得它记录字符间的相等关系，而丢弃字符的具体取值。

对于字符串 $s$，定义其形状序列为一个长度为 $|s|$ 的非负整数序列 $a$：

对于 $1\le i\le |s|$，

• 若字符 $s_i$ 在 $s$ 中首次出现，令 $a_i=0$；
• 若字符 $s_i$ 在 $s$ 中并非首次出现，那么在 $s[1,i-1]$ 中，找到所有字符的最后一次出现位置，从大到小记作 $j_1>j_2>\cdots >j_z$。如果 $s_{j_x}=s_i$，令 $a_i=x$。

于是，两字符串 $s,t$ 相似，当且仅当 $s$ 和 $t$ 的形状序列相同。

以下记 $n_0(a)$ 表示非负整数序列 $a$ 中 $0$ 的个数。

由定义可得，字符串的形状序列有以下性质：

1. 一个字符串的不同字符个数，等于其形状序列中 $0$ 的个数。
2. 设一个字符串的形状序列为 $a$，则 $n_0(a)\le k$，$\mathrm{\forall }1\le i\le |a|$，有 $a_i\le n_0(a[1,i-1])$。

对于非负整数序列 $a$，称 $a$ 是一个合法形状序列，当且仅当它满足以上两个条件。对于合法形状序列 $a$，恰有 $A_k^{n_0(a)}$ 个字符串的形状序列为 $a$，其中 $A_n^m$ 表示排列数 $\frac{n!}{(n-m)!}$。

对于合法形状序列 $a$ 和整数 $1\le l\le r\le |a|$，令 $a$ 关于区间 $[l,r]$ 的子形状序列为一个长度为 $r-l+1$ 的序列 $b$，满足：

对于 $1\le i\le r-l+1$， $b_i=\{\begin{array}{ll}{a}_{l+i-1},& a_{l+i-1}\le n_0(b[1,i-1]);\\ 0,& a_{l+i-1}>n_0(b[1,i-1]).\end{array}$

$$$a$ 关于区间 $[l,r]$ 的子形状序列记作 $\mathrm{subshape}(a,l,r)$。特殊地，对于不在上述范围内的 $l,r$，$\mathrm{subshape}(a,l,r)=ϵ$。

对于整数 $1\le l\le |a|+1$，$\mathrm{subshape}(a,l,|a|)$ 统称为 $a$ 的后缀形状序列。

那么，对于字符串 $s$ 和整数 $l,r$，设 $s$ 的形状序列为 $a$，则 $s[l,r]$ 的形状序列为 $\mathrm{subshape}(a,l,r)$。

显然，对于合法形状序列 $a$ 和整数 $l,r$，$n_0(\mathrm{subshape}(a,l,r))\le n_0(a)$。

算法二

用于解决 $n=1$，$L\le 1000$ 的数据。

将 $S_1$ 的所有后缀的形状序列插入Trie。对最终Trie的每个结点，统计其代表的形状序列对应的字符串数。

时间复杂度 $O\left(L^2\right)$，空间复杂度 $O\left(k{L}^2\right)$，期望得分 $9$ 分。

算法三

用于解决 $n=1$，$L\le {10}^5$ 的数据。

沿用后缀数组的思想，我们试图求出任意两个后缀的形状序列的 LCP，并比较字典序大小。

记 $S_1$ 的形状序列为 $A$，非空后缀 $S_1[l,|S_1|]$ 的形状序列为 $A^{(l)}$。

注意到，对于 $1\le i\le |S_1|-l+1$，$A^{(l)}$ 是在 $A[l,|S_1|]$ 上修改 $O(\mathrm{\Sigma })$ 个位置所成。所以求 $\mathrm{LCP}(A^{(l)},A^{(l^{\prime })})$ 并比较 $A^{(l)}$ 和 $A^{(l^{\prime })}$ 的字典序大小，只需处理特殊点，特殊点之间的部分可以用普通的后缀数组处理。这样，预处理时间复杂度 $O(nk)$，单次查询时间复杂度 $O(k)$。

考虑一个合法形状序列的左右非空前缀对应的字符串数量总和，可以按前缀里 $0$ 的个数分段讨论，查询时间复杂度 $O(k)$。

将 $A^{(1)},A^{(2)},\dots ,A^{(|S_1|)}$ 按照字典序从小到大排序，建这个“后缀数组”的笛卡尔树，叶子的前缀总和减掉 LCA 的前缀总和就是答案。

综上所述，这个算法时间复杂度 $O(kL\log L)$，空间复杂度 $O(kL)$，期望得分 $20$ 分。

算法四

用于解决 $k=2$，$L\le 1000$ 的数据。

我们考虑怎样的字符串是好的。那显然是在第一个字符串匹配最长的一个前缀，然后把剩下的部分丢到第二个里头匹配，依次类推。

不难想到一种思路，即构造一个自动机使得其恰好接受好的字符串，随后利用递推对其接受的字符串数计数。

对于每个字符串 $S_i$，令自动机 $M_i$ 为一棵 Trie。枚举 $f$，将 $S_i$ 的每个后缀作用 $f$ 后插入到 $M_i$ 上。则 $M_i$ 接受的字符串集合恰为 $C_i$。对于 $M_i$ 中没有的转移，我们把它连到 $M_{i+1}^{\prime }$ 的对应字符状态上，得到一个新自动机 $M_i^{\prime }$。最后 $M_1^{\prime }$ 接受的就是所有好的字符串。对 $M_1^{\prime }$ 所对应的 DAG 做路径计数即可。

这个算法，总时空复杂度 $O\left(L^2\right)$，期望得分 $15$ 分。

算法五

用于解决 $L\le 1000$ 的数据。

根据之前的分析，形状序列是我们判定字符串相似的有力工具。我们试图从形状序列入手。

还是令 $M_i$ 为一棵Trie，将字符串 $S_i$ 的所有后缀的形状序列插入到 $M_i$ 上。则 $M_i$ 能接受所有 $S_i$ 的子串的形状序列。记 $z_q$ 表示状态 $q$ 接受的合法形状序列中 $0$ 的个数。那么从 $q$ 出发的 $0$ 转移带权 $k-z_q$，别的带权 $1$。对于 $M_i$ 中没有的转移，我们把它连到 $M_{i+1}^{\prime }$ 的序列 $0$ 对应状态上，得到新自动机 $M_i^{\prime }$。

算法六

用于解决 $k\le 5$ 的数据。

在子形状序列意义下，如果 $B$ 和 $B^{\prime }$ 的右端点集合相同，且 $n_0(B)=n_0\left(B^{\prime }\right)$，那么用同一个状态接受 $B$ 和 $B^{\prime }$。类似后缀自动机的建法搞一个“子形状序列自动机”，然后把它们连接起来。状态和转移数都是 $O(kL)$。如果用数组存边，空间复杂度为 $O\left(k^{2}L\right)$，时间复杂度为 $O(kL)$。期望得分 $70$ 分。结合算法三，期望得分 $81$ 分。

算法七

如果两个状态的右端点集合相同但是 $0$ 的个数不同，那么除了 $0$ 的转移以外，别的有效转移都一样。对于普通的转移还是直接路径计数，对于两个自动机之间的连接边，可以用后缀和来转移同一个右端点集合的所有状态。时空复杂度 $O(kL)$，期望得分 $100$ 分。

三维立体混元劲

from EntropyIncreaser

实际上部分分和正解没有任何关系，我们就直接切入正题好了。

本题的核心就是解决高维多项式乘法时的维度爆炸问题。也就是根据传统方法，我们在计算多项式乘法 $f(x_1,\dots ,x_k)\cdot g(x_1,\dots ,x_k)mod(x_1^{n_1},\dots ,x_k^{n_k})$ 时，设 $N=\prod _i{n}_i$，若要先计算整个值域，则值域是 $\mathrm{\Omega }\left(N{2}^k\right)$ 量级的，更无论适合 DFT 的值域了。这里，我们提出一种时间复杂度为 $\mathrm{\Theta }(kN\log N)$ 的多项式乘法方法。

接下来我们将给出的算法颇具构造性。首先我们将一个下标 $(i_1,\dots ,i_k)$ 转化为一个「$(n_1,\dots ,n_k)$ 进制数」，即 $i=i_1+i_2\cdot n_1+\cdots +i_k\cdot n_1\cdots n_{k-1}$。这个转化有一个至关重要的好处，那就是 $(i_1,\dots ,i_k)$ 下标的加法对应于 $i$ 下标的加法。只不过现在我们需要去掉加法发生了进位部分的贡献。

一个直觉是，我们应当设置一个合适的占位多项式，也就是先考虑某个占位函数 $\chi (i)$ 使得 $i+j$ 不进位当且仅当 $\chi (i+j)=\chi (i)+\chi (j)$。那么，我们进行一个 $\sum _i{f}_i{x}^i{t}^{\chi (i)}$ 的二元多项式乘法，其乘法就可以使得我们提取出实际的结果了。

那么问题来了，什么样的 $\chi (i)$ 是较为合适的呢？借由子集卷积，容易想到的一者是 $\chi (i)=\sum _j{i}_j$，但当 $n_j$ 很大的时候，这会让 $\chi (i)$ 的值域非常大。我们不妨转换思维，如果对于每一个 $i$，都能保证 $\{\chi (i-j)+\chi (j)\mid 0\le j\le i\}$ 这个集合很小的话，我们就可以设置一个阈值 $D$ 然后 $mod(t^D-1)$，如果前述集合中每个数 $modD$ 互不相同，那么我们所要求的信息还是可以成功保留的。

而回顾衡量进位的单位，我们惊喜地发现 $\chi (i)=\lfloor \frac{i}{n_1}\rfloor +\lfloor \frac{i}{n_1{n}_2}\rfloor +\cdots +\lfloor \frac{i}{n_1\cdots n_{k-1}}\rfloor$ 是一个很好的占位函数。由于 $\lfloor \frac{i}{x}\rfloor +\lfloor \frac{j}{x}\rfloor -\lfloor \frac{i+j}{x}\rfloor \in \{-1,0\}$，自然有 $\chi (i)+\chi (j)-\chi (i+j)\in [-k+1,0]$。因此，我们只需计算 $\sum _i{f}_i{x}^i{t}^{\chi (i)}$ 在 $mod(t^k-1)$ 下的多项式乘法。因为 $k\le {\log }_{2}N$，比较好的实现是做 $k$ 个长为 $2N$ 的 DFT，然后在 $t$ 维暴力进行卷积，复杂度便为 $\mathrm{\Theta }(kN\log N)+\mathrm{\Theta }\left(k^{2}N\right)=\mathrm{\Theta }(kN\log N)$。

而在本题中，不难考虑到无向连通图和无向图的关系为 $G=\ln F$（其中都是 EGF）。只需考虑 $G^{\prime }=F^{\prime }/F$，我们需要计算多元幂级数的 $1/F$。事实上，我们有一个非常简洁的实现方式。我们先通过特殊进制数的转化，套用在一元多项式上常见的牛顿迭代法，然后卷积全部替换成前述的 $\mathrm{\Theta }(kN\log N)$ 的高维卷积即可。复杂度即为 $\mathrm{\Theta }(kN\log N)$。

其正确性亦不难解释，因为高维卷积已经被考虑为带有占位多项式的 $\sum _i{f}_i{x}^i{t}^{\chi (i)}$ 卷积，对其进行任何运算，只会产生一些 $j<\chi (i)$ 的 $x^i{t}^j$ 项，这些项不会再对形如 $x^i{t}^{\chi (i)}$ 项有贡献。因此我们实际上就是牛顿迭代的时候只维护这个多项式的 $\chi (i)$ 所构成的上轮廓。

另一点巧妙的地方在于，我们可以直接考虑一个特殊的微分算子 $\mathfrak{D}F$ 是 $\sum _{i}i{f}_i{x}^i$，不难检验它满足常见的导数性质（对多元幂级数 $f,g$ 有 $\mathfrak{D}(fg)=f\mathfrak{D}g+g\mathfrak{D}f$，以及对幂级数 $f$ 和多元幂级数 $g$ 有 $\mathfrak{D}(f\circ g)=(f^{\prime }\circ g)\cdot \mathfrak{D}g$），因此求导也可以保持一元多项式上的写法。

由此，我们得到了一种通用性极强的多元幂级数计算方法——而时间代价仅仅是乘以一个维数 $k$。

数圈圈

from Itst

算法一

枚举每条边的出边并暴力计算，复杂度 $O(n^n\mathrm{poly}(n))$，期望得分：$1$。

算法二

由于 $y=0$，故 $T$ 中不能有环，那么 $G^{\prime }(V,T)$ 形成了若干条链，$|T|=k$ 的方案数即为有 $n-k$ 条链的方案数。

对于每个有 $n-k$ 条链的方案，考虑对每个没有出度的点选一个没有入度的点向其连一条特殊边，使得整个图构成一个 $n$ 个点的环。这样做的方案数是圆排列方案数 $(n-k-1)!$。

这样可以把问题转化为：再在图上任意两个不同的点之间连一条特殊边，求所有哈密顿回路中特殊边数为 $k$ 的方案数。设 $f_{S,p,q}(1\in S)$ 表示覆盖点集 $S$ 的起点为 $1$、终点为 $p$、走过 $q$ 条特殊边的方案数，转移较为简单，最后判断 $f_{\{1,2,\cdots ,n\},p,q}$ 是否存在 $p\to 1$ 的边去贡献答案。复杂度 $O\left(2^n{n}^3\right)$，常数不大。结合算法一，期望得分：$15$。

算法三

对于 $A$ 单调不降、$y=1$ 的部分分，需要计算的即为选择 $k$ 条边的方案数。

枚举 $\{a_1,a_2,\cdots ,a_n\}$的一个长度为 $k$ 的子序列 $\{a_{p_1},a_{p_2},\cdots ,a_{p_k}\}$ 并计算 $p_1,p_2,\cdots ,p_k$ 有出边的方案数。从小到大考虑每一个点的出边。对于 $p_i(1\le i\le k)$，其有 $a_{p_i}$ 条出边可以选择，其中 $p_1\sim p_{i-1}$ 这 $i-1$ 个点使得 $1\sim a_{p_i}$ 中的 $i-1$ 个点有了入度，因此总共有 $a_{p_i}+1-i$ 条边选中后合法，且这个方案数与前 $i-1$ 个点的决策无关。

这样子序列 $\{a_{p_1},a_{p_2},\cdots ,a_{p_k}\}$ 对应的方案数即为 $\prod _{i=1}^k(a_{p_i}+1-i)$，需要求出所有长度为 $k$ 的子序列的方案数和。这是 LibreOJ 6073 小 Q 的序列 的拓展问题，在 杜老师的 ODE 博客 和我的论文中都有描述其做法。复杂度 $O(n{\log }^{2}n)$，需要稍微注意多点求值的常数。结合算法一、二，期望得分：$30$。

算法四

对于 $A$ 单调不降、$y\ne 1$ 的情况，考虑直接对算法三进行拓展。仍然考虑枚举一个长度为 $k$ 的子序列 $\{a_{p_1},a_{p_2},\cdots ,a_{p_k}\}$ 并计算其方案数。

认为一条边加入后若图上的环数增加，则其边权为 $y$，否则边权为 $1$，则一个图的权值为所有边的权值乘积。

按照编号从小到大的顺序依次确定每个点出边的权值和。对于 $p_i(1\le i\le k)$，有 $a_{p_i}+1-i$ 条出边可以选择。注意到当 $a_{p_i}<p_i$ 时，由于 $A$ 单调不降，$p_i$ 在图上一定没有入度，同时也不能连向自己，所以每条边权值都是 $1$；对于 $a_{p_i}\ge p_i$ 的情况，设 $u$ 为 $p_i$ 所在的链的起点，那么 $u\le p_i$，故边 $(p_i,u)$ 的权值是 $y$，其他边的权值是 $1$。

注意到 $p_i$ 的出边权值和不受 $p_1\sim p_{i-1}$ 的选择影响，因此整个序列的权值和就是每个点的权值和的乘积，即 $\prod _{i=1}^k(a_{p_i}+1-i+(y-1)[a_{p_i}\ge p_i])$，最后的处理和算法三类似。结合算法二期望得分：$55$。如果直接使用暴力 DP 计算答案，可以通过子任务一、二、三获得 $20$ 分。

算法五

对于 $A$ 单调不增的情况，可以考虑用倒序代替正序拓展算法四的推导，分解一个子序列的权值。

但直接做会出现一些问题，我们举例说明：$A=\{3,2,2\},p=\{2,3\}$。当 $3$ 的出边选择 $2$ 时，$2$ 是没有去往 $3$ 的边的，因此两条边权值都是 $1$；而 $3$ 的出边选择 $1$ 时，$(2,2)$ 的权值为 $y$。

这说明了在 $A$ 单调不增的情况下不能得到类似算法三、四中的“$p_i$ 的出边权值和不受 $p_1\sim p_{i-1}$ 影响”的结论，也就不能直接进行分解。

观察 $A$ 单调不增的情况的子任务，其中子任务八的特殊性质非常诡异，我们可以仔细考虑一下。

子任务八的限制条件可以描述为如下形式：考虑 $n$ 个边集 $E_1,\cdots ,E_n$，对于每一条边 $(i,j)$ 将其放在 $E_{min(i,j)}$ 中。这样对于非空的 $E_i$，可以用两个数 $p_i,q_i\ge i$ 代表它，意义为 $E_i=\{(i,x)\mid x\le p_i\}\cup \{(x,i)\mid x\le q_i\}$。由于 $a_i\ge b_i$，可以得到 $p_i\ge q_i$。

在这样的情况下，图上有边 $(j,i)$ 可以推出图上有边 $(i,j)$。对于这样的图，在从后往前考虑一个序列 $\{p_1,\cdots ,p_k\}$ 的出边情况下，考虑 $p_i$ 时，若图上有链 $p_{x_1}\to p_{x_2}\to \cdots p_{x_k=i}$ 且 $a_{p_i}\ge p_i$，则可以得到 $a_{p_i}\ge \underset{j=1}{\overset{k}{max}}{p}_{x_j}$，即 $p_i$ 往 $p_{x_1}$ 的边是存在的。

因此可以直接类比算法四的推导得到序列 $\{p_1,\cdots ,p_k\}$ 的权值和为 $\prod _{i=1}^k(a_{p_i}-k+i+(y-1)[a_{p_i}\ge p_i])$。沿用算法三、四的做法，结合算法二、四期望得分：$70$。

算法六

考虑将算法五进行拓展。对于任意单调不增的序列 $A$，设其对应图 $G$。定义对 $A$ 进行翻转操作即为做以下操作得到序列 $A^r$：将 $G$ 的 $E_1,\cdots ,E_n$ 得到后，对于每个 $i$ 若 $p_i<q_i$ 则交换两者，得到 $E_1^r,\cdots ,E_n^r$，然后利用这个新的边集还原得到图 $G^r$ 和对应的序列 $A^r$。

例如 $A=\{3,2,2\}$ 时，由于 $p_2=2,q_2=3$，对其进行翻转操作得到 $p_2=3,q_2=2$，还原后得到新的序列 $A^r=\{3,3,1\}$。

证明 $A^r$ 满足子任务八的限制是容易的。同时我们也可以证明存在一个双射 $\varphi :P(G)\to P\left(G^r\right)$，其中 $P(G)$ 表示 $G$ 中的所有简单有向链和简单环构成的集合，满足若 $T\in P(G)$，则：

1. $\varphi (T)$ 和 $T$ 覆盖相同的点集；
2. $\varphi (T)$ 是简单环当且仅当 $T$ 是简单环。

证明如下：

对 $v=\underset{|E_i|>0}{max}i$ 进行归纳。$v=0$ 时两图都没有边，只有长度为 $1$ 的链，取 $\varphi (\{v\})=\{v\}$。

结论对 $0$ 至 $v-1$ 均成立时，对于图 $G,G^r$，将点 $1$ 和边集 $E_1$ 删掉后得到的两个图 $G_1,G_1^r$ 满足 $G_1$ 翻转得到 $G_1^r$，因此存在双射 $\psi :P(G_1)\to P(G_1^r)$ 满足条件。

然后加入编号为 $1$ 的点和 $E_1$ 中的边。对于 $T\in P(G)$，若 $T\in P(G_1)$ 则 $\varphi (T)=\psi (T)$ 满足条件。否则考虑 $1$ 在 $T$ 中的情况以及 $G$ 变为 $G^r$ 的过程中是否翻转 $E_1$，$\varphi (T)$ 的取值如下表：

其中 $R_1,R_2$ 为属于 $P(G_1)$ 的某条简单有向链。用逗号将若干个路径或节点连接表示将它们拼接得到的简单有向链或简单环，其中情况三表示的是简单环，其余是简单有向链。

容易验证 $\varphi$ 的一对原像和像满足同时不是环或同时是环，且构成它们的点集是一致的，故只需要证明这样的连边不会导致某条边不属于 $G^r$ 即可。

对于 $R_1$ 或 $R_2$ 大小 $\le 1$ 的情况，其在 $\psi$ 下的像为其本身。在未翻转的情况下边没有发生改变，不会导致连边不存在；在翻转的情况下边的方向也发生了翻转，因此该边也是存在的。

对于 $R_1$ 或 $R_2$ 大小 $>1$ 的情况，可以利用“从 $1$ 能直接到达以及能直接到达 $1$ 的集合总是其他点的对应集合的超集”论证。由于情况较多仅举一例：

当 $T=1,R_1$ 且 $E_1$ 翻转时，设 $\psi (R_1)$ 的终止节点为 $w$ 且 $(w,1)\notin G^r$，即 $(1,w)\notin G$，故 $G$ 中 $w$ 没有入度，则 $w$ 一定是 $R_1$ 的起始节点。而 $T=1,R_1$ 意味着 $(1,w)\in G$ 产生矛盾，因此 $(w,1)\in G^r$，这条路径是合法路径。

对于其他情况可以类似证明。综合上面的讨论可以证明 $\varphi$ 的合法性。

所以最后只需要对 $A$ 做翻转操作得到 $A^r$ 然后使用算法五即可。总复杂度 $O(n{\log }^{2}n)$。综合算法四，期望得分：$100$。