HDU 6960 ¶

题意¶

有一个长度为\(n\)的环，三种颜色，要求绿色至多为\(k\)个，且相邻颜色不能相同，求旋转后本质不同的方案数。

\(3 \le n \le 10^6,0 \le k \le 10^6\)

令\(g(n,m)\)表示长度为\(n\)的串，有\(m\)个绿色（不考虑本质相同）的方案数。

则\(g(n,m)=2^m(C_{n-m}^m+C_{n-m-1}^{m-1})\)

\(2^m\)是在绿色的空隙之间插入另外两种颜色，一个空隙有两种方案。

两种情况：如果n位置没有放绿色，则方案为\(C_{n-m}^m\)，如果放了则为\(C_{n-m-1}^{m-1}\)（1和n-1都不能放）

\(g(n,0)=[n\%2=0]\times2\)（特殊情况）

由Burnside引理，

\(\frac1n\sum\limits_{i=1}^n \sum\limits_{j=0}^{\lfloor\frac{kgcd(i,n)}{n}\rfloor}g(gcd(i,n),j)\)

\(=\frac1n\sum\limits_{d=1}^{n}\sum\limits_{i=1}^n[gcd(i,n)=d] \sum\limits_{j=0}^{\lfloor\frac{kd}{n}\rfloor}g(d,j)\)

\(=\frac1n\sum\limits_{d=1}^{n}\varphi(\frac nd) \sum\limits_{j=0}^{\lfloor\frac{kd}{n}\rfloor}g(d,j)\)

后面这个求和暴力即可。

总复杂度\(O(\sum\limits_{d|n}\frac{kd}{n})\lt O(nlogn)\)