2018 EC Final B Mysterious … Host
题目链接注意到两个排列本质不同，当且仅当它们的析合树不同。所以我们就是要对所有有 $n$ 个叶子的析合树计数。考虑析合树的性质：首先析合树是区分儿子顺序的，所以我们会思考能否用生成函数去表示一棵树。设 $F(x)$ 表示析合树的生成函数，其中 $[x^m]F(x)$ 表示有 $m$ 个叶子的析合树的个数，我们先不考虑 $[x^0]F(x)$ 是啥，之后要用的时候再特殊定义。那么下一步我们要考...
题目链接注意到两个排列本质不同，当且仅当它们的析合树不同。所以我们就是要对所有有 $n$ 个叶子的析合树计数。考虑析合树的性质：首先析合树是区分儿子顺序的，所以我们会思考能否用生成函数去表示一棵树。设 $F(x)$ 表示析合树的生成函数，其中 $[x^m]F(x)$ 表示有 $m$ 个叶子的析合树的个数，我们先不考虑 $[x^0]F(x)$ 是啥，之后要用的时候再特殊定义。那么下一步我们要考...
A类似后缀数组算本质不同串的思路，考虑 $S$ 的第 $i$ 个前缀和第 $i+1$ 个前缀有多少个都会被计算，发现被算重的后缀等价于 $T$ 中 $S[i+1]$ 的出现次数。举个例子：abc abc 第 1 个前缀和第二个前缀都会算到 abc,原因是第一个前缀是 "a"+"bc"，第二个是 "ab"+"c"...
定义无穷数列 $<a_0,a_1,a_2,\ldots>$ 的一般生成函数（OGF）是定义在形式幂级数环上的形式幂级数 $A(z)=\sum_{i \geq 0} a_iz^i$，它对应的 指数生成函数（EGF）是 $\hat A(z)=\sum_{i \geq 0} a_i \frac{z^i}{i!}$一些常用的生成函数：那么答案的生成函数就是 $F(z) = MUL(F_n...
A. T1先观察一个性质：对于两个区间 $[l_i,r_i],[l_j,r_j]$，如果有 $l_i \leq l_j < r_j \leq r_i$，那么在最终的方案中不可能出现 $i$ 区间和 $j$ 区间不在一组，却和其他区间在一组的情况（可以把 $i$ 移动到 $j$ 所在的组，那么 $i$ 组答案不变劣，$j$ 组答案不变）于是我们考虑将区间分成两个集合：$A$ 集合内的区间...