Luogu4916 [MtOI2018] 魔力环

发表于 分类于 ， ， 阅读次数：

题意： 个珠子的手环满足如下条件：

  • 有 个黑色珠子， 个白色珠子。
  • 不存在大于 个连续的黑色珠子。

两个手环旋转后相同，则本质相同。求本质不同的手环的种类数。

答案对 取模，，时限 。

首先特判全黑的情况（）。

看到环与旋转，容易想到 Burnside 引理。

设 为旋转 步，符合题意的不动点个数。答案为

  • 引理：长度为 的环旋转 步后和自己相等。等价关系形成 个环，这些环大小相等，均匀交错。

设 为：不动点要求的等价关系形如 个交错环，填写黑白的方案数。则 。

现在考虑如何求 。

等价类（形如交错的环）的个数为 ，相当于点 的等价类编号为 。

如下 的情形：

1
0123 | 0123 | 0123

那么每连续 个元素（循环节）可以看成一个小环（大小为 )，因为左右能与其他一模一样的循环节相接。

就是：在小环上选择 个黑色（要求 ），不能有连续 个黑色的方案数。（已排除全黑，故这段“连续黑”不会串联多个环）

设 为：在一个大小为 的环上，染 个黑色，不能有超过 个连续黑色的方案数。

有

现在考虑如何求 。

考虑把 个黑球放进 个白球的 个空隙内。

由于是环，第一个空隙和最后一个空隙共享限制，它们的黑球个数加起来不过 。枚举它们共放多少个黑球：

其中 是：在 个盒子里放 个球，盒子容量上限为 的方案数。代表剩余的缝隙。

系数 是因为： 个球可以有一部分放在第一个空隙，一部分放在最后一个空隙。

考虑如何计算 。

考虑容斥。令某些盒子超过容量，容易发现盒子之间没有顺序关系，有：

其中， 为把 个球放进 个有标号盒子中的方案数，这用组合数学很好算。

复杂度分析。

容斥计算 的复杂度是 。

回看 ，需要求 个 ，复杂度。

回看 复杂度是 （ 的约数之和）。

注： - 易证 。因为约数最差情况下形如 - 进一步地，可证 。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <algorithm>
#include <cstdio>

const int MaxN = 100050, mod = 998244353;

int powM(int a, int t=mod-2) {
	int ret = 1;
	while(t) {
		if (t&1)
			ret = 1ll*ret*a %mod;
		a = 1ll*a*a %mod;
		t >>= 1;
	}
	return ret;
}
int fac[MaxN], ifac[MaxN];
int C(int n, int m) {
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void Init(int n) {
	fac[0] = 1;
	for (int i=1; i<=n; i++)
		fac[i] = 1ll*fac[i-1]*i %mod;
	ifac[n] = powM(fac[n]);
	for (int i=n; i; i--)
		ifac[i-1] = 1ll*ifac[i]*i %mod;
}

int T(int n,int m) {
	return C(n+m-1, n-1);
}
int K;
int R(int n,int m) {
	int ans=0;
	for (int i=0; i<=std::min(m/(K+1),n); i++) {
		if (i&1)
			ans =(ans-1ll*C(n,i)*T(n,m-i*(K+1))) %mod;
		else
			ans =(ans+1ll*C(n,i)*T(n,m-i*(K+1))) %mod;
	}
	return (ans+mod)%mod;
}
int S(int n, int m) {
	if (m<=K) return C(n,m);
	int ans = 0;
	for (int i=0; i<=std::min(K,m); i++)
		ans = (ans+1ll*R(n-m-1,m-i)*(i+1)) %mod;
	return ans;
}

int phi(int n) {
	int ans = n;
	for (int i=2; i*i<=n; i++)
		if (n%i==0) {
			ans=ans/i*(i-1);
			while(n%i==0)n/=i;
		}
	if (n>1) ans = ans/n*(n-1);
	return ans;
}
int gcd(int a, int b) {
	return !b ? a : gcd(b, a%b);
}

int main() {
	int n, m;
	scanf("%d%d%d", &n, &m, &K);
	if (n==m) {
		puts(K>=m ? "1" : "0");
		return 0;
	}
	Init(n);
	int D = gcd(n,m), ans = 0;
	auto calcFactor = [&ans,n,m](int d) -> void {
		ans = (ans + 1ll*S(n/d,m/d)*phi(d)) %mod;
	};
	for (int i=1; i*i<=D; i++)
		if (D%i==0) {
			calcFactor(i);
			if (i*i!=D)
				calcFactor(D/i);
		}
	ans = 1ll*ans*powM(n)%mod;
	printf("%d", ans);
	return 0;
}