英语课上，老师问你们认为的孤独是什么，轮到我的时候，我说：When I was asleep, she told me in the dream that you were awake

和班主任商量了一下，会考前就不去机房了。~~越来越像退役了~~

~~有点想陶陶~~

不过无聊了由于生物钟大概还是想看看OI？

把树上后缀排序看看

【模板】树上后缀排序

题目描述

给定一颗以 $1$ 为根包含 $n$ 个节点的树，保证对于 $2$ ~ $n$ 的每个节点，其父亲的编号均小于自己的编号。
每个节点上有一个的字符，一个节点所代表的字符串定义为从当前节点一直到根节点的简单路径上经过的所有字符连起来形成的字符串。
请你给这些字符串按照字典序排序。
特别地，如果两个节点所代表的字符串完全相同，它们的大小由它们的父亲所代表的字符串的大小决定（这句可能是废话），如果仍相同，则由它们编号的大小决定。

输入输出格式

输入格式：
第 $1$ 行包含一个正整数 $n$。
第 $2$ 行包含 $n-1$ 个数 $f_{2 \dots n}$，其中 $f_i$ 表示 $i$ 的父亲。
第 $3$ 行为一个包含 $n$ 个小写字母的字符串 $s$，其中 $s_i$ 表示编号为 $i$ 的节点上的字符。
输出格式：
输出一行 $n$ 个正整数，第 $i$ 个正整数表示代表排名第 $i$ 的字符串的节点编号。
输入输出样例

输入样例#1：
5
1 1 3 2
abbaa

输出样例#1：
1 5 4 2 3

说明

对于 $20\%$ 的数据，$1 \le n \le 10 ^ 3$。
对于 $50\%$ 的数据，$1 \le n \le 10 ^ 5$。
对于 $100\%$ 的数据，$1 \le n \le 5 \times 10 ^ 5$。

题解

$O(nlog^2n)$的做法比较简单，直接前缀Hash然后写个比较函数二分出LCP然后注意一些边界就可以直接stable_sort了。

$O(nlogn)$倍增+基数排序。

每次合并向上的$2^k$的权值直到根，注意当第二关键字相同时编号小的在前（第三关键字）

然后由于我一向没什么实现水平，只好又去看题解实现…嗯，原理确实是这样,实现好像用了两次基数排序。。。。如下

namespace SuffixArray {
    int sa[N], rk[N], rkk[N], tp[N], rk2[N], tx[N];

    inline void tsort(int *sa, int *rk, int *tp, int m)
	{
        for (int i = 0; i <= m; i++) tx[i] = 0;
        for (int i = 1; i <= n; i++) ++tx[rk[i]];
        for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
        for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i];
    }

    inline bool pd(int i, int t) {
        return tp[sa[i-1]] == tp[sa[i]] && tp[f[t][sa[i-1]]] == tp[f[t][sa[i]]];
    }

    inline void SA() {
        int p = 0;
        for (int i = 1; i <= n; i++) a[i] = s[i] - 'a' + 1, tp[i] = i;
        tsort(sa, a, tp, n);
        rk[sa[1]] = rkk[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++) {
            rk[sa[i]] = a[sa[i-1]] == a[sa[i]] ? p : ++p;
            rkk[sa[i]] = i;
        }
        for (int w = 1, t = 0; w < n; w <<= 1, ++t) {
            for (int i = 1; i <= n; i++) rk2[i] = rkk[f[t][i]];
            tsort(tp, rk2, sa, n);
            tsort(sa, rk, tp, p);
            swap(rk, tp);
            rk[sa[1]] = rkk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i++) {
                rk[sa[i]] = pd(i, t) ? p : ++p;
                rkk[sa[i]] = i;
            }
        }
    }
}

我宁愿写Hash+二分（雾

然后看了看一个多项式讲解

话说这里有个相当nice的多项式讲解！

Polymial

引言

在一类多项式理论中，常常会遇到 $F’=H(F)$ 的形式，有时可以通过 $EGF$ 求解
但像我这种只会暴力计数的选手经常会推出一个看起来只能分治 $FFT$ 的式子，实际上一些特殊的形式可以做到更优
前置技能
上面的PDF

一阶线性微分方程

齐次线性方程

形式

$\frac{dy}{dx}+P(x)y=0$

求解

$\begin{aligned} \frac{dy}{dx}+P(x)y=0 \\ \Rightarrow \frac{dy}{y}=-P(x)dx \\ \Rightarrow \int \frac{dy}{y}=c_1 -\int P(x)dx \\ \Rightarrow \ln |y|=c_1- \int P(x)dx \\ \Rightarrow y=C e^{-\int P(x)dx} \quad (C=\pm e^{c_1}) \end{aligned}$

非齐次线性方程

形式

$\frac{dy}{dx}+P(x)y=Q(x)$

求解
可以通过对应的齐次线性方程，使用常数变易法求解
设 $y=u(x) e^{-\int P(x)dx}$ ，则：

$\begin{aligned} \frac{dy}{dx}=\frac{du}{dx} e^{-\int P(x)dx} - u(x)P(x) e^{-\int P(x)dx} \\ \Rightarrow \frac{du}{dx} e^{-\int P(x)dx} - u(x)P(x) e^{-\int P(x)dx} + P(x)u(x) e^{-\int P(x)dx} =Q(x) \\ \Rightarrow \frac{du}{dx} = Q(x) e^{\int P(x)dx} \\ \Rightarrow \int du=C+\int Q(x) e^{\int P(x)dx} dx \\ \Rightarrow u(x)=C+\int Q(x) e^{\int P(x)dx} dx \\ \Rightarrow y= e^{-\int P(x)dx} \left( C + \int Q(x) e^{\int P(x)dx} dx \right) \\ \end{aligned}$

可以发现，等式右端第一项是对应的齐次线性方程的通解，第二项是非齐次线性方程的一个特解（在 $C=0$ 时取到）
即一阶非齐次线性方程的通解等于对应的齐次方程的通解与非齐次方程的一个特解之和
正文
考虑一类多项式微分方程：

$F'=H(F)$

一般来说只需要考虑模 $x^n$ 意义下的值即可
那么考虑倍增的过程，假设现在要求 $F{2n}$ ，那么可以先递归求解 $F{n}$
于是现在有：

$F' _ {n} \equiv H(F _ n) \pmod {x^n}$

考虑 $H$ 在 $F_{n}$ 处的泰勒展开，可以得到：

$F'_{2n} \equiv H(F_{2n}) \equiv H(F_n)+H'(F_n) (F_{2n}-F_{n}) \pmod {x^{2n}}$

整理可得：

$F'_{2n} \equiv \left( H(F_n)-H'(F_n)F_n \right) + H'(F_{n}) F_{2n} \pmod {x^{2n}}$

设 $y=F_{2n}$ ，可以得到：

$\frac{dy}{dx}+P(x)y=Q(x)$

于是可以得知它的一组解是：

$y=e^{-\int P(x) d x}\left(C+\int Q(x) e^{\int P(x) d x} d x\right)$

也就是：

$y=e^{\int H'(F_n)dx} \left( C+ \int \left( H(F_n)-H'(F_n)F_n \right) e^{- \int H'(F_n)dx} \right)$

例题

例1

这道题可能跟上面没啥关系
题目描述
求有多少个 $1 \sim n$ 的排列，使得环的大小都在 $A$ 中
其中 $1 \le n \le 10^5, 0 \le k \le n, 1 \le a_i \le n$
题解
设 $f_n$ 表示答案，则有：

$f_n=\sum_{i=1}^{n} {n-1 \choose i-1} f_{n-i} (i-1)![i \in A]$

设 $g_i=(i-1)![i \in A]$ ，则有：

$\begin{aligned} f_n=\sum_{i=1}^{n} {n-1 \choose i-1} f_{n-i}g_{i} \\ \Rightarrow \frac{f_n}{(n-1)!}=\sum_{i=0}^{n} \frac{f_{n-i}}{(n-i)!} \frac{g_i}{(i-1)!} \end{aligned}$

设 $[x^n]F(x)=\frac{f_n}{n!}$ ，且 $[x^n]G(x)=\frac{g_n}{(n-1)!}=[n \in A]$ ，则有：

$xF'(x)=F(x)G(x)$

设 $y=F(x)$ ，则有：

$y'+\frac{-G(x)}{x}y=0$

由于 $F(0)=1$ ，于是有：

$y=C \cdot e^{-\int \frac{-G(x)}{x} dx}=e^{\int \frac{G(x)}{x}dx}$

我感觉我只是抄了一遍公式，还不如学数分实在。。。

接下来就又是文化课时光了。

不存在的，再看一道题。

毒瘤之神TM菱树2

题目背景

什么?菱树是什么??
好吧这个是蒟蒻自己搞事搞的一个非常简单的不是树但很像树的图..
就像这样..

lingtree

(好吧图有点大(空旷)..)

注意：最短路径有多条只算一遍

题目描述

现在给你$T$棵菱树,每一颗菱树的层数为$n_i$,请求出菱树中所有点对的最短路径的和..
输入输出格式
输入格式：
第一行一个正整数$T$
接下来$T$行每一行一个正整数$n_i$表示菱树的大小..
输出格式：
$T$行,每行一个整数表示对于当前这颗菱树的所有点对的最短路径的和模$998244853$的结果.
输入输出样例

输入样例#1：
5
1
2
3
4
5

输出样例#1：
0
4
43
225
812

说明
${\rm Subtask\ 1(10\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 10$
${\rm Subtask\ 2(20\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 100$
${\rm Subtask\ 3(30\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 1000$
${\rm Subtask\ 4(40\ pts)}: 1 \leq T \leq 10000 \qquad 1 \leq n_i \leq 5*10^6$
为了防止打表，所以空间限制缩小至64MB。

题解

首先观察可知，最短路径就是去掉多余边的树上的简单路径。而且是个稀疏图

直接暴力建图$O(n^2logn)$求出所有最短路然后按照层枚举点对这样就可以$O(n^2)$算出所有1到n的答案，就有$60$pts啦。

然后推推式子。

第一种是在图中选择的两个点一个在这一层的下方，一个在这一层的上方。
根据$T4$的最短路的结论，我们可以推断出这种情况只可能通过这一层一次。
第二种是两个点都在这一层的下方。
这样一上一下，肯定要经过两次。
那么直接计算这一层的贡献。
首先第一种的方案非常好求。就是这一层上面的节点个数$\times$下面的节点个数$\times$权值。转化为式子就是:

$\sum\limits_{i=1}^{n}\frac{i \times (i+1)}{2} \times (\frac{n \times (n + 1)}{2} - \frac{i \times (i+1)}{2}) \times i$

第二种的话。。
首先可以多画几个草图，发现需要满足右边的点到这一层的距离需要大于或等于左边的点与右边的点在该层从左往右数的相对位置的差。
事实上如果推出了$T4$的三种情况，那这个还是挺好想到的。
那么这样的话我们就考虑枚举左边的点。然后右边可以选择的点就是一个公差为$(n-i)$的等差数列。然后左边每一列的点一共有$(n-i)$个，则可以得到方案数为：

$\sum\limits_{i=1}^n(n-i)^2 \times \frac{i \times (i+1)}{2}$

然后由于需要一上一下，所以答案需要乘上一个$2 i$。
综上所述，最后的答案就是

$\sum_{i=1}^{n-1} \frac{i \times (i+1)}{2} \times (\frac{n \times (n + 1)}{2} - \frac{i \times (i+1)}{2}) \times i + (n-i)^2 \times i ^ 2 \times (i+1)$

复杂度$O(N^2)$
$Subtask 4$
还是用上面的式子。也许可以化简一下变成$O(N)$
我们把它拆分一下:

$\frac{n \times (n + 1)}{2} \times \sum_{i=1}^{n-1}(\frac{i \times (i+1)}{2} \times i) - \sum_{i=1}^{n-1} ((\frac{i \times (i+1)}{2})^2 \times i) + \sum_{i=1}^{n-1} (n^2-2\times i \times n +i^2) \times i ^ 2 \times (i+1))$ $= \frac{n \times (n + 1)}{2} \times \sum_{i=1}^{n-1}(\frac{i \times (i+1)}{2} \times i) - \sum_{i=1}^{n-1} ((\frac{i \times (i+1)}{2})^2 \times i) + n ^ 2 \times \sum_{i=1}^{n-1} (i ^ 2 \times (i + 1)) - 2\times n \times \sum_{i=1}^{n-1} (i ^ 3 \times (i+1)) + \sum_{i=1}^{n-1}(i ^ 4 \times (i+1))$

然后发现所有$\sum$里面的东西都可以$O(N)$递推，所以答案也可以$O(N)$递推了。

这题解抄的。。。