染色
szm_
·
·
个人记录
题意：
你可以选择其中任意连续的 $ L $ 个球然后把它们循环移位。两种染色方案是本质相同的当且仅当可以通过这种操作变成相同的。
求有多少种本质不同的染色方案。答案对 $ 10^9+7 $ 取模。
前置知识：
burnside引理：
$\frac{1}{|G|}\sum_{i=1}^{|G|} P_i
其中 P_i 代表第 i 个变换的不动点个数。注意：这里的变换包含了染色和移位。
polya定理：
\frac{1}{|G|}\sum_{i=1}^{|G|} m^{c_i}
其中 m 为颜色数， c_i 代表第 i 个变换的循环节（互不相交）个数。这里的变换不包含染色。
（特殊意义下的循环节：当变换为置换时，循环节个数就是环的个数。）
第一类无符号斯特林数：
（本题用到的）性质： $ \sum_{i=0}^{n} s(n,i) * x^i = x ^ {n↑} $ ，其中 $ x ^ {n↑} $ 表示的是 $x$ 的上升幂，即 $ \prod_{i=0}^{n-1} (x+i) $ 。
题解：
~~根据zzq的说法~~ 我们可以得知 $n=L$，$L$是奇数或偶数是三种不同的情况。~~（因此这题其实是三合一）~~
1. $n=L$。这个时候置换是所有的循环移位，共 $n$ 个。我们知道对于循环移 $i$ 位的置换，循环节个数需要满足 $k|i,k|n$，也就是 $gcd(i,n)$ 。因此套进polya也就是 $\frac{1}{n} * \sum_{i=0}^{n-1} K^{gcd(i,n)}$ 。
2. $L$是偶数。这种情况下如果 $L=2$，置换为任意排列。若$L\geq 4$ ，那么问题可以转化为能否构造出交换相邻两个。
显然如果 $L \neq n-1$，那么可以把剩余的部分依次通过交换向前推，把问题简化成 $L = n-1$。那么先把需要交换的那一对与开头对齐，以两个数的中间为起点做一次操作，就可以达到一对交换其余不变。（下面有示例）
所以这种情况只和每个颜色用了几次有关。做一个插板：$H_{n+1}^{k-1} = C_{n+k-1}^{n}
| A |
B |
C |
D |
X |
| B |
C |
D |
A |
X |
| X |
B |
C |
D |
A |
其中A,X交换。
-
那么式子变为 $\frac{2}{n!} * \sum_{i=0}^{n} s(n,i) * K ^ i * [ n == i \mod{2} ]$，其中 $i$ 是环的个数。
设 $F(k) = \frac{2}{n!} * \sum_{i=0}^{n} s(n,i) * K ^ i$ 。 那么 $n-i$ 为奇数可表示为 $ A * F(k) $，偶数为 $ B * F(k) $，其中 $A,B$ 均为多项式， $A=\frac{1-(-1)^n}{2}$， $B=\frac{1+(-1)^n}{2}$ 。显然有 $A-B=(-1)^n$。
$Ans=F(k) * A = \frac{F(k) + F(-k) * (A-B)}{2} = \frac{1}{n!} * \sum_{i=0}^{n} s(n,i) * K ^ i $ 。
根据性质，有 $ \sum_{i=0}^{n} s(n,i) * K^i = K ^ {n↑} $。
因此， $Ans=\frac{K^{n↑}}{n!}$ 。
终于写完啦！
P.S. 话说我发现zzq的课件式子有错qwq，多除了个2，后来发现是burnside那个 |G| 他算的是 n!，实际上我们也可以看到我上面是 |G| = \frac{n!}{2} ，这个原因是奇排列和偶排列实际上是一样多的，证明是只要交换前两个元素，就可以实现奇排列和偶排列的一一映射。