Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP2150 [NOI2015] 寿司晚宴

Posted on In
Symbols count in article: 2.4k Reading time ≈ 2 mins.

毒瘤根号分治出处

寿司晚宴

思路

考虑 dp ，设 $d[S_1][S_2]$ 表示“第一个人选的质数集合为 $S_1$ ，第二个人为 $S_2$ 的方案数”，枚举每个数转移，显然为 $O(n 2^{\mid S \mid})$ ，问题在于 $\mid S \mid$ 太大

用根号分治，考虑到 $\le \sqrt{n}$ 的质数由且仅有 $8$ 个，且每个数最多含一个 $> \sqrt{n}$ 的质数，我们可以把每个数处理成小质数集合 + 一个大质数的形式，然后 dp

考虑如何保证大质数，不妨排序（保证大质数相同的在一其），那么大质数相同的就只有一个人能选，我们另设 $f_1[S_1][S_2]/f_2[S_1][S_2]$ 表示“该大质数由 $1/2$ 号来选，且第一个人选的质数集合为 $S_1$ ，第二个人为 $S_2$ 的方案数”，初值就是 $d[S_1][S_2]$ ， dp 完成后，再让 $d[S_1][S_2] = f_1[S_1][S_2] + f_2[S_1][S_2] - d[S_1][S_2]$ ，这里再减一下说因为该大质数相同的数一个都不选的方案被算了两遍

代码

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
#include <bits/stdc++.h>
#define STC static
#define FF std::function
using LL = long long;
const int N = 500 + 100, B = 19, V = (1 << 8);
const int id[20] = {0, 0, 1, 2, 0, 3, 0, 4, 0, 0, 0, 5, 0, 6, 0, 0, 0, 7, 0, 8};
int n;
LL p, d[V + 100][V + 100], ans;
struct Node{ int sm, bg; } a[N];
void adj(LL &x){ x += (x >> 63) & p; }
void prev()
{
	FF<void(Node&, int)> ins = [&](Node &x, int pr){ (pr <= B) ? x.sm |= (1 << (id[pr] - 1)) : x.bg = pr; };
	STC int vis[N], pri[N], ct;
	for (int i = 2; i <= n; ++i)
	{
		if (!vis[i]){ pri[++ct] = vis[i] = i, ins(a[i], i); }
		for (int j = 1; j <= ct && pri[j] * i <= n; ++j)
		{
			if (vis[i] < pri[j]) break;
			vis[i * pri[j]] = pri[j];
			a[i * pri[j]].sm |= a[i].sm; //这里调了我半天
			a[i * pri[j]].bg = a[i].bg;
			ins(a[i * pri[j]], pri[j]);
		}
	}
}
void dp(int l, int r)
{
	STC LL f1[V + 100][V + 100], f2[V + 100][V + 100];
	std::memcpy(f1, d, sizeof d), std::memcpy(f2, d, sizeof d);
	for (int i = l; i <= r; ++i)
		for (int j = V - 1; ~j; --j)
			for (int k = V - 1; ~k; --k) if (!(j & k))
			{
				if (f1[j][k] && !(k & a[i].sm)) adj(f1[j | a[i].sm][k] += f1[j][k] - p);
				if (f2[j][k] && !(j & a[i].sm)) adj(f2[j][k | a[i].sm] += f2[j][k] - p);
			}
	for (int j = 0; j < V; ++j)
		for (int k = 0; k < V; ++k) if (!(j & k)) adj(d[j][k] = -d[j][k]), adj(d[j][k] += f1[j][k] - p), adj(d[j][k] += f2[j][k] - p);
}
int main()
{
	scanf("%d %lld", &n, &p), prev();
	std::sort(a + 2, a + n + 1, [&](Node x, Node y){ return x.bg < y.bg; });
	d[0][0] = 1, a[n + 1].bg = a[n + 1].sm = -1; //防越界
	int i = 2;
	if (!a[2].bg) //特判没有大质数
		for (; !a[i].bg; ++i)
			for (int j = V - 1; ~j; --j)
				for (int k = V - 1; ~k; --k) if (d[j][k])
				{
					if (!(k & a[i].sm)) adj(d[j | a[i].sm][k] += d[j][k] - p);
					if (!(j & a[i].sm)) adj(d[j][k | a[i].sm] += d[j][k] - p);
				}
	for (int j = i; a[j].bg != -1; ++i) if (a[i].bg != a[j].bg) dp(j, i - 1), j = i;
	for (int j = 0; j < V; ++j)
		for (int k = 0; k < V; ++k) if (!(j & k) && d[j][k]) adj(ans += d[j][k] - p);
	printf("%lld\n", ans);
	return 0;
}