洛谷P2561 [AHOI2002] 黑白瓷砖题解

题目链接：P2561 [AHOI2002] 黑白瓷砖

题意：

输入格式：

一行，一个正整数 $n(n \leq 20)$ 。

输出格式：

以一行的形式输出问题的解 $s$ （解的位数不超过 $200$ 位）。

这个题面也是有点难绷，而且洛谷上连最后那张图片都没贴。

显然这道题考察了 Pólya 定理，搬个介绍过来吧（~~不会这个还做这道题？~~）。

$\mathcal{Part}\ 1$

Burnside 引理

设 $A,B$ 为有限集合，$X$ 为一些从 $A$ 到 $B$ 的映射组成的集合。

$G$ 是 $A$ 上的置换群，且 $X$ 中的映射在 $G$ 中的置换作用下封闭。

$X / G$ 表示 $G$ 作用在 $X$ 上产生的所有等价类的集合，则

$|X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^g\right|$

其中 $X^g=\{x \mid x \in X,~g(x)=x\}$ 。

Pólya 定理

在与 Burnside 引理相同的前置条件下，若 $X$ 为所有从 $A$ 到 $B$ 的映射，则

$|X / G|=\frac{1}{|G|} \sum_{g \in G}|B|^{c(g)}$

其中 $c(g)$ 表示置换 $g$ 能拆分成的不相交的循环置换的数量。

$\mathcal{Part}\ 2$

注意到旋转的两种和翻转的三种实际上包括了旋转又翻转得到的置换

因此 $|G|=6$ ，分别为单位元一种、旋转的两种、翻转的三种。以及显然 $|B|=2$ 。

那么 $c(g)$ 怎么算呢？不妨记瓷砖的个数为 $N=\frac{n(n+1)}{2}$ 。

对于旋转操作，由于旋转三次以后就会回到原点，所以循环大小为 $3$ ，得到循环数量为 $c(g)=\left\lceil\frac{N}{3}\right\rceil$ 。

为什么是上取整呢，因为比如 $n=4$ 的情况，中间会有一个点不动，可以看作一个大小为 $1$ 的循环。
对于翻转操作，注意到除了对称轴上的 $\left\lceil\frac{n}{2}\right\rceil$ 个点，其余的点均为两两交换，故循环大小为 $2$

那么不相交的循环置换的数量就是这几个不动的加上剩下的点除以 $2$ ，即 $c(g)=\frac{N-\left\lceil\frac{n}{2}\right\rceil}{2}+\left\lceil\frac{n}{2}\right\rceil$ 。
对于单位元，大家都不动，那就是 $c(g)=N$ ，非常简单。

于是答案就是

$\mathrm{Ans} = \frac{1}{6}\times \left(2^N + 2\times 2^{\left\lceil\frac{N}{3}\right\rceil} + 3\times 2^{\left(\frac{N-\left\lceil\frac{n}{2}\right\rceil}{2}+\left\lceil\frac{n}{2}\right\rceil\right)}\right)$

时间复杂度 $\mathcal{O}(200\log N)$ ，python 整数幂自带快速幂

代码：

n = int(input())
N = n * (n + 1) // 2

_1 = 2 ** N
_2 = 2 * 2 ** ((N + 2) // 3)
_3 = 3 * 2 ** ((N - ((n + 1) // 2)) // 2 + (n + 1) // 2)
print((_1 + _2 + _3) // 6)