本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-01 21:24:40

首先发现这个过程很类似埃筛，每个数把它的所有倍数筛掉。

然后可以知道，有的数字是不能被其他数字筛掉的，比如任何质数都不可能被其他数筛掉。当然，这只是个充分不必要条件。

可以把这些不能被别的数筛掉的数，叫做唐数。

然后发现 $t(p)$ 本质上就是 $p$ 排列中最后面的那个唐数的位置。

我们可以考虑枚举这个最后的位置，然后来算贡献。

设 $w$ 表示唐数的数量，这可以用类似筛法的东西 $O(n\lg\lg n)$ 预处理出来。

枚举这个最后的位置 $x$：

它本身肯定要选一个唐数，方案数是 $w$；

后面一个唐数也不能选，也就是把剩下的 $n - w$ 个不同的数分配给 $n - w$ 个位置，所以方案数是 ${n-x\choose n-w} (n-w)!$；

前面是任意选的，方案数是 $(x - 1)!$

所以一个 $x$ 的贡献是

$$xw{n-x\choose n-w}(n-w)!(x-1)!$$