Doremy 的钉子游戏题解

思路

设 $t=\lfloor n/2\rfloor$。按橡皮筋第一次被中心钉子挡住时两侧仍保留的端点分类，可以把一个合法数组唯一分解为：选择旋转起点、选择跨过中心的方向与宽度、选择若干可自由穿插的钉子，再排列已经移除的钉子。

固定分类参数 $i$ 后，方向与宽度共有 $2t-i$ 种；除偶数 $n$ 的最后一种边界外，可自由选择的钉子数为 $n-i-2$。若从中选择 $j$ 个，贡献为组合数乘 $(i+j-1)!$。最后乘上 $n$ 个旋转起点并求和。

小规模可以直接枚举子集与排列。中等规模可以按组合数定义逐项重算。满分做法预处理阶乘和逆阶乘，使每个组合数在常数时间求出。

做法

预处理 $0!$ 到 $n!$，并利用 $p$ 为质数且 $n<p$，通过费马小定理求逆阶乘。

枚举 $i$ 从 $\lfloor n/2\rfloor$ 到 $n-1$。当 $n$ 为奇数时跳过 $i=n-1$。令

$$u=\begin{cases} 0,&i=n-1,\\ n-i-2,&\text{其他情况}. \end{cases}$$

再枚举 $0\le j\le u$，把

$$n(2\lfloor n/2\rfloor-i)\binom{u}{j}(i+j-1)!$$

加入答案并始终对 $p$ 取模。

复杂度

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。