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;
}