HDU6960. Necklace of Beads题解

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;
}
上一篇:容斥原理(基本形式及其证明)


下一篇:JSON(02)JQuery中JSON的解析与应用