题解：AT_abc268_g [ABC268G] Random Student ID

期望是假的。只需要求每种字典序下的排名和。再除以 $26!$ 即真实答案。

考虑排名的定义。在一种字典序的定义下，如果存在 $j$ 个字符串 $k$ 满足 $S_k < S_i$。那么 $i$ 的排名就是 $j+1$。

所以只需要对于每个对 $(i, k)$（$i \ne k$），计算有多少种字典序的定义满足 $S_k < S_i$。将这个值累加进 $i$ 的答案。最后输出时别忘 $+1$ 才能得到真实排名。

那么问题是，有多少种字典序的定义能满足 $S_k < S_i$ 呢？

分类讨论一下：

- 如果 $S_k$ 是 $S_i$ 的前缀。那么 $26!$ 种方案都合法。
- 否则，如果 $S_i$ 是 $S_k$ 的前缀。那么合法方案数为 $0$。
- 否则，令 $l = \operatorname{lcp}(S_i,S_k)$。那么一定有 $l + 1
\le \min( |S_i|, |S_k|)$，而且 $S_{i,l+1} \ne S_{k,l+1}$。不难发现只要确定了 $S_{i,l+1}, S_{k,l+1}$ 的大小关系就能确定 $S_i,S_k$ 的大小关系。

我们希望 $S_k < S_i$，也就是在字典序的定义里，$S_{k,l+1}$ 需要比 $S_{i,l+1}$ 更靠前。不难发现总共的 $26!$ 种方案里，恰有一半满足这个条件。也就是说方案数为 $26!/2$。

于是得到了一个简单平方级别的解决方案。考虑优化。

注意到，我们只需要求有多少 $k$ 满足是 $S_i$ 的前缀，以及有多少 $k$ 满足 $S_i$ 是 $S_k$ 的前缀。知道这两个值，也就是前两种情况的方案数后，第三种情况可以用 $n$ 减出来。

形式化的，令有 $a$ 个 $k$ 满足 $S_k$ 是 $S_i$ 的前缀，$b$ 个 $k$ 满足 $S_i$ 是 $S_k$ 的前缀，则：

$$
ans_i = 26! \times a + 0 \times b + (n-a-b)\times 26!/2
$$

而 $a, b$ 的求解见 [字典树](https://www.luogu.com.cn/problem/P8306)。

代码：<https://atcoder.jp/contests/abc268/submissions/59691152>

正在渲染内容...