CF1630E 题解

题意

传送门

一个长度为 $ n $ 的环状序列 $ {a_i} $ ，其中的数值满足 $ 1\leq a_i\leq n $ ，序列中可能有相等的数。

序列 $ {a_i} $ 的一个排列和另外一个排列本质相同，当且仅当可以通过旋转使它们变得每一项都对应相等。

对于 $ {a_i} $ 的任何一种本质不同排列，可以构造一张 $ n $ 个点的无向图，节点 $ i $ 对应序列中的 $ a_i $ 。若序列中相邻两项相等（首项和末项也相邻），则在它们的对应的节点之间连一条边。这个排列的价值为无向图的连通块数量。

给定序列 $ {a_i} $ ，从它的所有本质不同排列中等概率选择一个，求价值的期望。

\(1\le n\le10^6\)。

题解

计数，一生之敌……

先考虑没有循环同构条件时的答案。用 \(c_1,c_2,\dots c_m\) 表示各数值的出现次数，总排列数显然为 \(S=\dbinom{n}{c_1,c_2,\dots c_m}\)。连通块个数等于相邻且不同的元素对数，可以枚举这两个数值 \(x,y\) 以及它们的位置，于是总连通块个数为 \(T=\sum\limits_{x\neq y}n\dbinom{n-2}{c_1,\dots ,c_x-1,\dots ,c_y-1,\dots ,c_m}\)。答案为 \(\frac{T}{S}\)。

再考虑有循环同构条件。解决循环同构的利器是 Burnside 引理，先尝试解决 \(S\)。\(S=\dfrac{\sum_{i=1}^nf_i}{n}\)，其中 \(f_i\) 表示旋转 \(i\) 单位时不变的排列个数。稍微做过几道 Burnside 的题目就会知道此时序列被分割为 \(\gcd(i,n)\) 个相互独立的环，环上所有元素要求相等。于是 \(f_i=g_{\gcd(i,n)}\)，其中 \(g_i=\dbinom{i}{\frac{c_1}{n/i},\frac{c_2}{n/i},\dots,\frac{c_m}{n/i}}\)。

参考上面的思路，枚举 \(x,y\) 的值及位置，\(T=\dfrac{\sum_{i=1}^nh_{\gcd(i,n)}}{n}\)，其中 \(h_i=\sum\limits_{x\neq y}n\dbinom{i-2}{\frac{c_1}{n/i},\dots,\frac{c_x}{n/i}-1,\dots,\frac{c_y}{n/i}-1,\dots,\frac{c_m}{n/i}}\)。注意前面的系数，为什么是 \(n\) 不是 \(i\)？因为环上的元素相等，如果 \(a_p\) 与 \(a_{p+1}\) 不相等，\(a_{p+i}\) 与 \(a_{p+1+i}\) 也不相等。\(i\times\frac{n}{i}=n\)。化一下式子，\(h_i=\sum\limits_{x\neq y}\frac{f_ic_xc_yn}{i(i-1)(n/i)^2}\)，而 \(\sum c_xc_y\) 易求，于是可以速算。

设枚举了 \(t\) 次 \(i\)，复杂度为 \(O(tm)\)。但由于 \(i|c_1,c_2,\dots c_m,n\)，这个值并不大。于是此题得解。