[Mivik Round / Secret Sky] [题解] 魔女的茶会

· · 题解

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 / 代码