- NFLS1015D
一个环，\(n\) 个点，\(m\) 个点染色，至多连续 \(k\) 个点被染色，求循环同构本质不同染色数。
\(\begin{alignedat}{3} \frac{\sum_{i=1}^nG(i)}{n}&=\frac{\sum_{i=1}^n f(\gcd(n,i),\frac{m\gcd(n,i)}{n})}{n} \\&=\frac{\sum_{d|n,n|md} f(d,\frac{md}{n})\sum_{i=1}^n [\gcd(i,n)=d]}{n} \\&=\frac{\sum_{d|n,n|md} f(d,\frac{md}{n})\sum_{i=1}^\frac{n}{d} [\gcd(i,\frac{n}{d})=1]}{n} \\&=\frac{\sum_{d|n,n|md} f(d,\frac{md}{n})\phi(\frac{n}{d})}{n} \\&=\frac{\sum_{d|n,d|m} f(\frac{n}{d},\frac{m}{d})\phi(d)}{n} \\&=\frac{\sum_{d|\gcd(n,m)} f(\frac{n}{d},\frac{m}{d})\phi(d)}{n} \end{alignedat}\)
\(f(n,m)\) 表示 \(n\) 个点，\(m\) 个点染色，首尾相加和中间连续的至多有 \(k\) 个点，考虑有 \(n-m\) 个未染色的，那么插空写出生成函数。
\(F(x)=(\sum_{i=0}^k x^i)^{n-m-1}(\sum_{i=0}^k(i+1)x^i)\)，前半部分是中间的，后半部分是首尾的。