P4562 游戏

__ryp__ · 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 的贡献是