自动搬运

查看原文

来自洛谷，原作者为

	Mivik AFO

搬运于2025-08-24 22:30:42，当前版本为作者最后更新于2021-04-15 23:53:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Subtask 1

这不就一种吗？

Subtask 2

这不就 $n^2$ 种吗？

Subtask 3

我会爆搜！

Subtask 4

考虑 $n$ 是奇数。我们把棋盘 $45$ 度旋转一下然后按列标号，像这样（$n=5$）：

    5
   4 6
  3 5 7
 2 4 6 8
1 3 5 7 9
 2 4 6 8
  3 5 7
   4 6
    5

不难发现，第 $i$ 列（$1\le i<n$）和第 $i+n$ 列会互相掌控，第 $i$ 行和第 $i+n$ 行也会互相掌控，我们改写一下上面那个棋盘，把第 $i+n$ 行都接到第 $i$ 行末尾，并把标号为 $i+n$ 的改成标号为 $i$，于是变成了

5 2 4 1 3
4 1 3 5 2
3 5 2 4 1
2 4 1 3 5
1 3 5 2 4

也就是说，我们现在需要在这个矩阵中选 $m$ 个互不相同的数，且这些数不在同一行。我们发现这个矩阵每行每列都不包含相同的数，这个结论实际上可以简单讨论得到。显然任意改变一行内数的顺序不会影响答案，我们完全可以把上面那个矩阵排为

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

于是这个问题就变成了，在一个 $n\times n$ 的棋盘上选 $m$ 个位置，这些位置没有任意两个在同一行或同一列。考虑枚举用到了哪些行和哪些列后剩下的方案数就是 $m!$，于是答案为

$$\binom nm^2m!$$

Subtask 5

考虑 $n$ 是偶数的情况。这种情况我们发现黑格和白格（也就是按行号与列号的奇偶性分组）互不相关，我们可以分开考虑。更进一步地，不难发现旋转后黑格部分和白格部分是完全相同的，也就是说在它们上面放棋子的方案数相同，我们只需要考虑任意一种。

我们沿袭上面的方法把一种格子提出来标号（$n=6$）：

  34
 2345
123456
 2345
  34

然后第 $i$ 列（$1\le i\le n/2$）和第 $i+n/2$ 列会互相掌控，第 $i$ 行和第 $i+n/2$ 行也会互相掌控，我们改写棋盘：

312312
231231
123123

对行重排：

112233
112233
112233

我们发现每个 $[0,n/2]$ 间的数字恰在每行出现了两次，这也是易证的。我们考虑选出 $m$ 个互不相同且不在同一行的数，选第 $k$ 个数是我们恰有 $n-2(k-1)$ 种方案，于是在黑格 / 白格中放 $k$ 个棋子的方案数就是

$$\begin{aligned}&\binom{n/2}k\prod_{i=1}^k(n-2(i-1))\\=&\binom{n/2}k2^k\prod_{i=1}^k(n/2-(i-1))\\=&\binom{n/2}k2^k(n/2)^{\underline k}\\=&\binom{n/2}k^22^kk!\end{aligned} $$

于是最终的答案就是

$$\begin{aligned} &\sum_{i=0}^k\binom{n/2}i^22^ii!\cdot\binom{n/2}{k-i}2^{k-i}(k-i)!\\ =&2^k\sum_{i=0}^k\binom{n/2}i^2\binom{n/2}{k-i}^2i!(k-i)! \end{aligned} $$

预处理阶乘后直接计算即可。

Subtask 6

把关于 $n$ 的部分改成下降幂：

$$2^k\sum_{i=0}^k\left(\frac{(n/2)^{\underline i}(n/2)^{\underline{k-i}}}{i!(k-i)!}\right)^2i!(k-i)! $$

预处理下降幂后直接计算即可。

mivik.h / 代码