HDU6960. Necklace of Beads

题意:

有一串由红、绿、蓝三种颜色的珠子组成的项链，珠子数为\(n\)​​个。

问：在旋转后一样的情形只算一种的条件下，有多少种情况满足相同颜色不相邻且绿珠子不超过\(k\)个。

分析：

题目中对绿色的个数有限制，又有旋转同构的问题存在。

为了方便描述，不妨设\(g(n,m)\)​​​​​为长度为\(n\)​​​​​的环里有\(m\)​​​​​​个绿色且满足相邻位置颜色不相同的方案数（先不考虑旋转产生的同构，即旋转后一样的话也算多种情况），显然不考虑同构的话，答案就应该是\(\sum\limits_{m=0}^kg(n,m)\)​

接下来解决旋转同构的问题，

给这个环编号为\(0,1,2,\dots,n-1\)​​​，设\(\varphi_i\)​​​为循环位移\(i\)​​​位，

则有

\[\begin{aligned} \varphi_i(x)&= (x+i) \% n \end{aligned} \]

显然\(\varphi_i\)​是一个置换，\(\{\varphi_0,\varphi_1,\varphi_2,\dots,\varphi_{n-1}\}\)​构成了一个\(n\)​元置换群（这里有\(n\)个不同的置换）

我们知道，置换一定能写成不相交轮换之积，所以考虑对于\(\varphi_i\)​​​​​​​能写成怎样的不相交轮换之积。

我们考虑从位置\(x\)​​​选定一个方向开始走，每次步长为\(i\)​​​，即只能走长度为\(i\)​​​的倍数，现在要走回\(x\)​​​，你只能走长度为\(n\)​​​的倍数，故最少经过\(\frac{\mathrm{lcm}(n,i)}{i}\)​​​步，你才能返回\(x\)​​​。而\(\frac{\mathrm{lcm}(n,i)}{i} = \frac{n}{\gcd(n,i)}\)​​​，所以对于\(\varphi_i\)​​来说，拆成轮换的长度应该是\(\frac{n}{\gcd(n,i)}\)​​，由于\(x\)​​是任取的，所以\(\varphi_i\)​​能够写成\(\gcd(n,i)\)​​个\(\frac{n}{\gcd(n,i)}\)​​​​​​​​轮换之积。

具体来说，可以写成

\[\begin{aligned} \varphi_i=&(0,i,2i,\cdots,\frac{ni}{\gcd(n,i)})\\ &(1,1+i,1+2i,\cdots,1+\frac{ni}{\gcd(n,i)})\\ &\cdots\\ &(\gcd(n,i)-1,\gcd(n,i)-1+i,\cdots,\gcd(n,i)-1+\frac{ni}{\gcd(n,i)})\\ &\text{（为了简洁上面的加号和乘号都是模$n$意义下的）} \end{aligned} \]

那么对于\(\varphi_i\)​这个置换来说，有哪些情况通过它置换后是实际上是一样的（即不动点数量）。

显然需要处于同一个轮换中的那些位置颜色相同，由于相邻颜色不能相同，故上面式子里相邻轮换的颜色也不能相同，且最后一个轮换和第一个轮换颜色也不能相同，所以此时相当于求在长度为\(\gcd(n,i)\)​​​​的环里绿色数量满足一定条件且相邻颜色不同的方案数，即

\[\sum\limits_{j=0}^{?}g(\gcd(n,i),j) \]

特殊地，如果\(\gcd(n,i)=1\)​​，相当于只有一个轮换，此时这个轮换里的颜色是不能相同的，此时应该有\(g(\gcd(n,i),j)=0\)​​，然而我们将\(g(\gcd(n,i),j)\)​理解为，长度为\(1\)的环里绿色数量满足一定条件且相邻颜色不同的方案数可不可以呢？此时我们可以认为是可以的，因为我们可以认为长度为\(1\)​的环，第一个的颜色和最后一个的颜色相同，然而这是不合法的，故情况数为\(0\)，不影响正确性。

注意到我求和号的上限写了个问号，这个细节需要注意。

那么这个问号到底应该是多少呢？由于题目要求绿色数不超过\(k\)个的方案，而一个轮换的长度是\(\frac{n}{\gcd(n,i)}\)，所以\(j\)怎么样都不能超过\(\left\lfloor \frac{k}{n/\gcd(n,i)}\right\rfloor\)个，所以问号就应该是\(\left\lfloor \frac{k}{n/\gcd(n,i)}\right\rfloor\)​

所以对于\(\varphi_i\)而言，有下式这么多的情况，经过\(\varphi_i\)置换后，实际上是一样的

\[\sum\limits_{j=0}^{\left\lfloor \frac{k}{n/\gcd(n,i)}\right\rfloor}g(\gcd(n,i),j) \]

根据Burnside引理，答案为所有置换的不动点数量的平均数，即为

\[\frac{1}{n}\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{\left\lfloor \frac{k}{n/\gcd(n,i)}\right\rfloor} g(\gcd(n,i),j) \]

接下来考虑\(g(n,m)\)​该如何计算。

我们分两种情况考虑，

• \(m=0\)​时，此时没有绿色，只有蓝色和红色，此时要让相邻颜色不相同，只有当\(n\)​为偶数时才做得到，并且不考虑旋转同构的情况下，有蓝红蓝红……和红蓝红蓝……两种填法。

• \(m\neq 0\)​​​​时，我们分步考虑，首先我们要在长度为\(n\)​​​​的环里，选择\(m\)​​​​​​个不相邻的位置（不考虑旋转同构）

  对于第一步，环的问题比较复杂，我们先从长度为\(n\)​的链，选择\(m\)​​个不相邻的位置来考虑

  这个问题可以等价的认为，在\(n-m\)个数造成的\(n-m+1\)个间隙（最左边和最右边也算）中，插入\(m\)个数（每个间隙只能插一个）的方案数，故答案为\(\mathrm{C}_{n-m+1}^{m}\)

  ！！注意：对于环，千万不能等价的认为\(n-m\)个数造成的\(n-m\)​​个间隙中，插入\(m\)个数，因为不考虑旋转同构，即旋转同构需要重复计算。

  对于环我们可以分为两种情况，给这个环编号为\(0,1,2,\dots,n-1\)​​​​

  • 选择了\(n-1\)​号为绿色，此时\(0,n-2\)​都不能选，此时只能从\(1,2,\dots,n-3\)​中选\(m-1\)​个不相邻的，此时方案数为\(\mathrm{C}_{n-3-(m-1)+1}^{m-1}=\mathrm{C}_{n-m-1}^{m-1}\)​​

  • 不选择\(n-1\)号为绿色，此时只能从\(0,1,\dots,n-2\)中选\(m\)个不相邻的，此时方案数为\(\mathrm{C}_{n-1-m+1}^m=\mathrm{C}_{n-m}^m\)​

  选完\(m\)​​个绿色之后，会出现\(m\)​​​​​个间隙，对于每个间隙里面只能填蓝色和红色两种颜色，要让相邻颜色不相同，只能填蓝红蓝红……或者红蓝红蓝……两种填法。

  所以\(m\)个间隙\(2^m\)种填法。

综上所述

\[g(n,m)=\begin{cases} 0,&m=0,n\text{为奇数}\\ 2,&m=0,n\text{为偶数}\\ 2^m(\mathrm{C}_{n-m}^m+\mathrm{C}_{n-m-1}^{m-1}),&\text{其它} \end{cases} \]

接下来我们考虑怎么算

\[\frac{1}{n}\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{\left\lfloor \frac{k}{n/\gcd(n,i)}\right\rfloor} g(\gcd(n,i),j) \]

不妨枚举从\(1\)到\(n\)枚举最大公约数，设\(d=\gcd(n,i)\)，原式变成

\[\begin{aligned} \text{原式} &=\frac{1}{n}\sum_\limits{d|n}\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{\left\lfloor \frac{kd}{n}\right\rfloor} [\gcd(n,i)==d]g(d,j)\\ &=\frac{1}{n}\sum_\limits{d|n}\sum\limits_{j=0}^{\left\lfloor \frac{kd}{n}\right\rfloor}\sum\limits_{i=0}^{n-1} [\gcd(n,i)==d]g(d,j)\\ &=\frac{1}{n}\sum_\limits{d|n}\sum\limits_{j=0}^{\left\lfloor \frac{kd}{n}\right\rfloor}\varphi\left(\frac{n}{d}\right)g(d,j)\\ &=\frac{1}{n}\sum_\limits{d|n}\varphi\left(\frac{n}{d}\right)\sum\limits_{j=0}^{\left\lfloor \frac{kd}{n}\right\rfloor}g(d,j)\\ &\text{其中，$\varphi(x)$为欧拉函数} \end{aligned} \]

故可以考虑预处理\(\varphi(x)\)​​​，阶乘，阶乘逆元，\(2^x\)​​​次方等数据，假设\(n\)​​​的因子数为\(\sigma_0(n)\)​​​，则可以使用\(O(n\sigma_0(n))\)​​​​​的算法来求得答案。

对于因子个数上界问题，可以参考n的正因子个数d(n)有没有上界公式？ - TravorLZH的回答 - 知乎，实际上远小于任何次数的多项式。

代码：

#include <cstdio>
typedef long long Lint;
const Lint mod = 998244353;
const int maxn = 1e6 + 10;
const int maxm = 1e6;
Lint prime[maxn], vis[maxn], phi[maxn];
Lint p[maxn], fac[maxn], invfac[maxn], inv[maxn];
void init() {
    phi[1] = p[0] = fac[0] = invfac[0] = inv[1] = fac[1] = invfac[1] = 1;
    p[1] = 2;
    for (Lint i = 2; i <= maxm; i++) {
        if (!vis[i]) {
            prime[++prime[0]] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= prime[0] && i * prime[j] <= maxm; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
        fac[i] = (i * fac[i - 1]) % mod;
        p[i] = (p[i - 1] * 2LL) % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        invfac[i] = invfac[i - 1] * inv[i] % mod;
    }
}
Lint C(Lint n, Lint k) {
    if (n < 0 || k < 0 || k > n)
        return 0;
    return fac[n] * invfac[k] % mod * invfac[n - k] % mod;
}
void solve() {
    Lint n, k;
    scanf("%lld%lld", &n, &k);
    int ans = 0;
    for (Lint d = 1; d <= n; d++) {
        if (n % d == 0) {
            int sum = d & 1 ? 0 : 2;
            for (Lint j = 1; j <= k * d / n; j++) {
                sum = (sum + p[j] * (C(d - j, j) + C(d - j - 1, j - 1)) % mod) %
                      mod;
            }
            ans = (ans + phi[n / d] * sum) % mod;
        }
    }
    printf("%lld\n", ans * inv[n] % mod);
}
int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}