VEXOBEN
Vexoben
Apr 3, 2019
It takes 46 minutes to read this article.

终于意识到动规的水平差得一批了。这边开个小专题练一下。

题目列表是学长 frank_c1 的博客。这样一来可以保证质量,二来也有自己能看懂的题解。

事实上很多题意也是贺的

这里还是挂个链接吧:orz

(刷新以获取数学公式)

[APIO 2014] Beads and wires

题意

在达芬奇时代,有一个流行的儿童游戏称为连珠线。当然,这个游戏是关于珠子和线的。线是红色或蓝色的,珠子被编号为 $ 1​ $ 到 $ n​ $ 。这个游戏从一个珠子开始,每次会用如下方式添加一个新的珠子:

  • $ Append(w, v)​ $ :一个新的珠子 $ w​ $ 和一个已经添加的珠子 $ w​ $ 用红线连接起来。
  • $ Insert(w, u, v) $ :一个新的珠子 $ w $ 插入到用红线连起来的两个珠子 $ u $ , $ v $ 之间。具体过程是删去 $ u $ , $ v $ 之间红线,分别用蓝线连接 $ u $ , $ w $ 和 $ w $ , $ v $ 。

每条线都有一个长度。游戏结束后,你的最终得分为蓝线长度之和。

给你连珠线游戏结束后的游戏局面,只告诉了你珠子和链的连接方式以及每条线的长度,没有告诉你每条线分别是什么颜色。

你需要写一个程序来找出最大可能得分。即,在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的,然后输出最大可能得分。

数据范围: $ 1≤n≤200000​ $

题解

如果确定一个点为根,我们可以且仅可以进行一个操作:选择两条有父子关系的边,将他们同时染蓝。

$ O(n^2) $ 的 $ DP $ 就是枚举根, $ f_{x,0/1} $ 表示 $ x $ 这棵子树中, $ x $ 到它父亲这条边 用了/没用 能产生的最大贡献。

方程列出来发现可以换根 $ DP​ $ ,操作一下就做完了。

(事实上我一开始用点分治做了换根 $ DP​ $ 做的事情,虽然本质上一样,但是一个上午都没调出来)

#include<bits/stdc++.h>
#define LL long long
#define pii pair<LL, LL>
using namespace std;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;

int n, m, E;
int fir[N], nex[N << 1], arr[N << 1], len[N << 1], flen[N];
LL ans, f[N][2];
set<pii> Set[N];

void Add_Edge(int x, int y, int l) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y; len[E] = l;
}

void dfs(int x, int fa) {
	f[x][0] = f[x][1] = 0;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		int y = arr[i];
		flen[y] = len[i];
		dfs(y, x);
		f[x][1] += max(f[y][0], f[y][1]);
		Set[x].insert(make_pair(max(f[y][0], f[y][1]) - flen[y] - f[y][1], arr[i]));
	}
	if (Set[x].size()) {
		f[x][0] = f[x][1] - (Set[x].begin() -> first) + flen[x];
	}
}

void dfs2(int x, int fa) {
	ans = max(ans, f[x][1]);
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		int y = arr[i];
		LL f0 = f[y][0], f1 = f[y][1];
		f[x][1] -= max(f0, f1);
		Set[x].erase(make_pair(max(f0, f1) - len[i] - f[y][1], y));
		f[x][0] = 0;
		if (Set[x].size()) {
			f[x][0] = f[x][1] - (Set[x].begin() -> first) + len[i];
		}
		f[y][1] += max(f[x][0], f[x][1]);
		f[y][0] = f[y][1];
		Set[y].insert(make_pair(max(f[x][0], f[x][1]) - len[i] - f[x][1], x));
		dfs2(y, x);
		Set[y].erase(make_pair(max(f[x][0], f[x][1]) - len[i] - f[x][1], x));
		f[y][1] = f1;
		f[y][0] = f0;
		f[x][1] += max(f0, f1);
		Set[x].insert(make_pair(max(f0, f1) - len[i] - f[y][1], y));
		f[x][0] = f[x][1];
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; ++i) {
		int x, y, l;
		scanf("%d%d%d", &x, &y, &l);
		Add_Edge(x, y, l);
		Add_Edge(y, x, l);
	}
	dfs(1, 0);
	dfs2(1, 0);
	cout << ans << endl;
	return 0;
}

[ZJOI 2017] 仙人掌

题意

给定 $ n $ 点 $ m $ 边的简单无向连通图。

现在要在图上加若干边,要求加边后还是一个简单无向连通图,且每条边至多属于一个简单环。

求加边方案数对 $ 998244353​ $ 取模的值。

$ 1≤n≤500000​ $ , $ 1≤m≤1000000​ $

题解

如果原图是不是仙人掌,答案为 $ 0​ $ 。

一张图为仙人掌当且仅当 $ dfs $ 树上的边最多被非树边覆盖 $ 1 $ 次。

已经被覆盖过的树边不能再次被覆盖。直接断开这些边,问题就转化为树上的情况。

因为不能有重边,所以问题就相当于:选出若干长度不小于 $ 2​ $ 的路径,每条边不能被覆盖超过 $ 1​ $ 次,求方案数。

这里一个关键的转化是,上述问题等价于:用若干条长度不小于 $ 1 $ 的路径,覆盖每条边恰好一次。

用 $ f_x​ $ 表示子树 $ x​ $ 的答案, $ g_x​ $ 表示子树 $ x​ $ 中,存在且仅存在一条从 $ fa_x​ $ 引下的链,其余边都被覆盖的方案数。

这里我转移时又糊了假算法。我加入一棵子树后直接转移,如果 $ x $ 保留了来自 $ y $ 的链,现在加入子树 $ z $ ,要么 $ y $ 和 $ z $ 连转移到 $ f_x $ ,要么 $ z $ 和 $ x $ 连转移到 $ g_x $ ,但是忽略了可以同时保留 $ y,z $ 两条链,分别和后面 $ u,v $ 两条相连的情况,于是过不了大样例

转移时先处理出一个数组 $ h​ $ , $ h_n​ $ 表示 $ n​ $ 棵子树,每棵子树有 $ 1​ $ 条从 $ x​ $ 引下的链,处理到所有边都被覆盖的方案数。

转移就很显然了,设 $ x $ 的儿子个数为 $ cnt $ :

$ h_0 = h_1 = 1, \;\; h_n = h_{n-1} + (n-1) h_{n-2} (n≥2) $

$ f_x = h_{cnt} \Pi_{fa_y = x} g_y $

$ g_x = f_x + \sum_{fa_y = x} h_{cnt - 1} \Pi_{fa_z = x} g_z $

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int M = 2e6 + 10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;

int n, m, E;
int h[N], f[N], g[N], vis[N], tag[N];
int fir[N], nex[M], arr[M], del[M], dep[N];

inline void Add_Edge(int x, int y) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y; del[E] = 0;
}

int dfs(int x, int pre) {
	int res = 0;
	vis[x] = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (!vis[arr[i]]) {
			dep[arr[i]] = dep[x] + 1;
			res += dfs(arr[i], i);
		}
		else if ((i ^ 1) != pre && vis[arr[i]] && dep[x] > dep[arr[i]]) {
			++res, --tag[arr[i]];
			del[i] = 1;
			del[i ^ 1] = 1;
		}
	}
	res += tag[x];
	if (res) {
		del[pre] = 1;
		del[pre ^ 1] = 1;
	}
	if (res > 1) return -inf;
	return res;
}

int add(register int x, register int y) {
	static int z;
	return ((z = (x + y)) >= mod) ? z - mod : z;
}

void dfs2(int x) {
	vis[x] = 1;
	int cnt = 0, s = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (vis[arr[i]] || del[i]) continue;
		dfs2(arr[i]);
		++cnt;
		s = 1LL * s * g[arr[i]] % mod;
	}
	if (!cnt) {
		f[x] = 1;
		g[x] = 1;
	}
	else if (cnt) {
		f[x] = 1LL * s * h[cnt] % mod;
		g[x] = add(f[x], 1LL * cnt * h[cnt - 1] % mod * s % mod);
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	memset(tag, 0, sizeof(int) * (n + 1));
	memset(vis, 0, sizeof(int) * (n + 1));
	memset(fir, 0, sizeof(int) * (n + 1));
	E = 1;
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		Add_Edge(x, y);
		Add_Edge(y, x);
	}
	if (dfs(1, 0) < 0) return (void) (puts("0"));
	memset(vis, 0, sizeof(int) * (n + 1));
	int ans = 1;
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		dfs2(i);
		ans = 1LL * ans * f[i] % mod;
	}
	printf("%d\n", ans);
}

int main() {
	int T;
	cin >> T;
	h[0] = h[1] = 1;
	for (int i = 2; i < N; ++i) {
		h[i] = add(h[i - 1], 1LL * (i - 1) * h[i - 2] % mod);
	}
	while (T--) solve();
	return 0;
}

[ZJOI 2012] 波浪

垃圾出题人卡我空间卡我常数卡我题意卡我精度。

虽然题目本身不错但是输出 $ 30 $ 位小数不取模是几个意思?

题意

阿米巴和小强是好朋友。

阿米巴和小强在大海旁边看海水的波涛。小强第一次面对如此汹涌的海潮,他兴奋地叫个不停。而阿米巴则很淡定,他回想起曾经的那些日子,事业的起伏,情感的挫折……总之今天的风浪和曾经经历的那些风雨比起来,简直什么都不算。

于是,这对好朋友不可避免地产生了分歧。为了论证自己的观点,小强建立了一个模型。他海面抽象成一个 $ 1​ $ 到 $ N​ $ 的排列 $ P[1…N]​ $ 。定义波动强度等于相邻两项的差的绝对值的和,即:

$ L = abs( P_2 – P_1 ) + abs( P_3 – P_2 ) + … + abs( P_N – P_{N - 1} ) $ 给你一个 $ N $ 和 $ M $ ,问:随机一个 $ 1…N $ 的排列,它的波动强度不小于 $ M $ 的概率有多大?

答案请保留小数点后 $ K​ $ 位输出,四舍五入。

数据范围:当 $ n≤50​ $ 时, $ k≤30​ $ ;当 $ n≤100​ $ 时, $ k≤8​ $

题解

考虑拆掉那个绝对值。这只需要从小到大依次加入每个数,每次加入时确定这个数旁边有几个数已经被加入计算贡献即可(例如加入 $ 5​ $ 时,它左边已经有数就会产生 $ +5​ $ 的贡献,右边还没有数就会产生 $ -5​ $ 的贡献)。

用 $ f_{i,j,k,l} $ 表示已经加入了前 $ i $ 个数,加入的数形成了 $ j $ 个连续段,当前产生的贡献是 $ k $ ,左右边界中有 $ l $ 个已经填了数。

需要注意的是,除了那些顶到左右边界的段,其它段我们只关心它们的相对位置。也就是说段是可以滑动的。

  1. 加入一个数时,有这样几种情况要考虑:
  2. 加入的数自成一段,且没有顶到左右边界,方案有 $ (j+1-l) $ 种。因为这个新段不能插入左端点左边或右端点右边。
  3. 加入的数自成一段,且顶到左右边界中的一个,方案有 $ (2-l) $ 种.
  4. 加入的数在某一段的左右端点,且没有顶到左右边界,方案有 $ (2j-l) $ 种。
  5. 加入的数在某一段左右端点,且顶到左右边界,方案有 $ (2-l) $ 种。
  6. 加入的数链接了相邻的两段,方案有 $ (j-1)​ $ 种

因为出题人的毒瘤,在 $ k=8 $ 时要用 $ long \; double $ 才能不被卡常,在 $ k=30 $ 时要用 $ float128 $ 才能不被卡精。

#pragma GCC optimize("2,Ofast,inline")
#pragma GCC optimize("-ffast-math")
#include<bits/stdc++.h>
#define R register
using namespace std;
const int N = 101;
const int S = 5005;

int n, m, k;
long double g[2][N][S * 2][3];
__float128 f[2][N][S * 2][3];

void write(__float128 x) {
	int a[100];
	a[0] = (int) x;
	for (int i = 1; i <= k + 1; ++i) {
		x -= (int) x;
		x *= 10;
		a[i] = (int) x;
	}
	if (a[k + 1] >= 5) ++a[k];
	for (int i = k; i >= 1; --i) {
		if (a[i] == 10) {
			a[i] = 0;
			++a[i - 1];
		}
	}
	printf("%d", a[0]);
	putchar('.');
	for (int i = 1; i <= k; ++i) printf("%d", a[i]);
	puts("");
}

template <typename T> void solve(T f[2][N][S * 2][3]) {
	int now = 1;
	f[0][0][S][0] = 1;
	R T v;
	for (int i = 1; i <= n; ++i) {
		memset(f[now], 0, sizeof f[now]);
		for (int j = 0; j <= n; ++j) {
			for (R int k = 0; k < 2 * S; ++k) {
				for (R int l = 0; l < 3; ++l) {
					v = f[now ^ 1][j][k][l];
					if (v == 0) continue;
					f[now][j + 1][k - i * 2][l] += v * (j + 1 - l);
					if (l < 2) {
						f[now][j + 1][k - i][l + 1] += v * (2 - l);
						f[now][j][k + i][l + 1] += v * (2 - l);
					}
					if (j) {
						f[now][j][k][l] += v * (j * 2 - l);
						f[now][j - 1][k + i * 2][l] += v * (j - 1);
					}
				}
			}
		}
		now ^= 1;
	}
	__float128 ans = 0;
	for (int i = m + S; i < 2 * S; ++i) {
		ans += f[now ^ 1][1][i][2];
	}
	for (int i = 1; i <= n; ++i) ans /= i;
	write(ans);
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	if (n == 1) {
		write(1);
		return 0;
	}
	if (m >= n * (n + 1) / 2) {
		write(0);
		return 0;
	}
	if (k <= 8) solve(g);
	else solve(f);
	return 0;
}

[ZJOI 2013] 蚂蚁寻路

题意

给定一个 $ n×m​ $ 的带权网格。

要求在网格中选出一个封闭图形。具体可以用一条路线描述。

开始位置在某一格点上,方向朝向北。接着右转两次,左转两次,右转两次,左转两次…… 最后再右转一次。规定这条路线上,不能连续旋转两次,不能经过重复的点,最后需要回到起始点,且左转的次数除以 $ 2 $ 等于 $ k $ 。

求所有能选出的图形中,点权和最大的是多少。

$ 1≤n,m≤100,0≤k≤10,abs(A_{i,j})≤10^4 $

题解

可以发现,原问题相当于选出 $ 2k+1 $ 个矩形,这些矩形的底边在一条直线上,且高度高低起伏,最大化他们的权值和。

枚举一个底边 $ down​ $ ,设 $ f_{i,j,l}​ $ 表示做到第 $ i​ $ 列,当前矩形高度为 $ j​ $ ,用了 $ l​ $ 个矩形的方案数。下一个矩形应变高还是变低可以通过 $ l​ $ 的奇偶性确定。

设 $ sum_{x1,y1,x2,y2}​ $ 表示左上角在 $ (x1,y1)​ $ ,右下角在 $ (x2,y2)​ $ 矩形的价值,只考虑变高的情况,一个直观的转移是:

$ f_{i,j,l} = \max_{x≤i-1,y>j} {f_{x,y,l-1} + sum_{j,x,down,i}} $

然而复杂的转移是阻碍优化的根源。如果我们把矩阵数量这一维的贡献算在这个矩阵的第一列上,可以得到更简洁的转移方程:

$ f_{i,j,l} = \max{f_{i-1,j,l},\max_{j’ > j} {f_{i-1,j,l-1}}} + sum_{j,i,down,i} $

这显然可以前缀和优化,得到 $ O(n^3k) $ 的优秀算法(这里认为 $ n,m $ 同阶)

#include<bits/stdc++.h>
#define R register
using namespace std;
const int N = 105;
const int inf = 0x3f3f3f3f;

int n, m, k;
int a[N][N], sum[N][N];
int f[N][N][25], g[N][N][25], h[N][N][25];

void upd(int &x, int y) {
	x = max(x, y);
}

int solve(int n) {
	for (int i = 0; i <= m; ++i) {
		for (int j = 0; j <= n + 1; ++j) {
			for (int l = 0; l <= k; ++l) {
				f[i][j][l] = -inf;
				g[i][j][l] = -inf;
				h[i][j][l] = -inf;
			}
		}
		f[i][n + 1][0] = 0;
	}
	for (int i = 0; i < m; ++i) {
		for (int l = 0; l <= k; ++l) {
			g[i][0][l] = -inf;
			for (int j = 1; j <= n; ++j) {
				upd(g[i][j][l], g[i][j - 1][l]);
				upd(g[i][j][l], f[i][j - 1][l]);
			}
		}
		for (int l = 0; l <= k; ++l) {
			h[i][n + 1][l] = -inf;
			for (int j = n; j >= 1; --j) {
				upd(h[i][j][l], h[i][j + 1][l]);
				upd(h[i][j][l], f[i][j + 1][l]);
			}
		}
		for (int j = 1; j <= n; ++j) {
			for (int l = 1; l <= k; ++l) {
				f[i + 1][j][l] = f[i][j][l];
				if (l & 1) upd(f[i + 1][j][l], h[i][j][l - 1]);
				else if (~l & 1) upd(f[i + 1][j][l], g[i][j][l - 1]);
				f[i + 1][j][l] += sum[j][i + 1] - sum[n + 1][i + 1];
			}
		}
	}

	int ans = -inf;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			upd(ans, f[i][j][k]);
		}
	}
	return ans;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	k = k * 2 + 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		for (int j = n; j >= 1; --j) {
			sum[j][i] = sum[j + 1][i] + a[j][i];
		}
	}
	int ans = -inf;
	for (int i = 2; i <= n; ++i) ans = max(ans, solve(i));
	cout << ans << endl;
	return 0;
}

[ZJOI2013]话旧

题意

有一个长度为 $ n+1 $ 的序列 $ A_0,A_1,…,A_n $ ,满足下列条件。

  1. $ A_0=A_n=0 $ 。

  2. 对于 $ 0≤i≤n−1 $ , $ abs(A_i−A_{i+1})=1 $ 。

  3. 对于所有极小值点 $ k $ ,有 $ A_k=0 $ 。

我们还规定了 $ A $ 的 $ m $ 个位置的值。

求满足条件的序列个数 和 序列最大值的最大值。第一问的答案对 $ 19940417 $ 取模。

数据范围: $ 1≤n≤10^9,0≤k≤10^6 $

题解

思维难度不是很高,主要在于分讨非常多。

设 $ f_{i,0/1} $ 表示到第 $ i $ 个关键点,最后一次是向下/向上的方案数; $ mx_{i,0/1} $ 表示到第 $ i​ $ 个关键点,最后一次是向下/向上的最大值。

转移就不想写了。看看代码就好了。要特别注意关键点纵坐标是 $ 0 $ 的情况;计算 $ mx $ 时,有些可以在坐标轴上平移直线来简化计算(大不了就是解 $ O(1) $ 个二元一次方程)

#include<bits/stdc++.h>
#define pii pair<int, int>
#define R register
using namespace std;
const int N = 1e6 + 10;
const int mod = 19940417;

int n, m;
int f[N][2], mx[N][2];
pii a[N];

inline void upd(int &x, int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

inline void chmax(int &x, int y) {
	x = max(x, y);
}

int Qpow(int x, int p) {
	if (p < 0) return 0;
	int ans = 1;
	while (p) {
		if (p & 1) ans = 1LL * ans * x % mod;
		x = 1LL * x * x % mod;
		p >>= 1;
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	a[++m] = make_pair(0, 0);
	a[++m] = make_pair(n, 0);
	sort(a + 1, a + m + 1);
	m = unique(a + 1, a + m + 1) - a - 1;
	f[1][1] = 1;
	for (int i = 2; i <= m; ++i) {
		int x0 = a[i - 1].first + a[i - 1].second;
		int x1 = a[i].first - a[i].second;
 		int d = (x1 - x0) / 2;
		int ds = a[i].first - a[i - 1].first;
		int dh = a[i].second - a[i - 1].second;
		if (a[i].second == 0) {
			if (a[i - 1].second == 0) {
				upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d - 1) % mod);
				chmax(mx[i][1], mx[i - 1][1]);
				chmax(mx[i][1], d);
			}
			else {
				if (d == 0) {
					upd(f[i][1], f[i - 1][0]);
					chmax(mx[i][1], mx[i - 1][0]);
				}
				else {
					upd(f[i][1], 1LL * f[i - 1][0] * Qpow(2, d - 1) % mod);
					chmax(mx[i][1], mx[i - 1][0]);
					chmax(mx[i][1], d);
				}
				upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d) % mod);
				chmax(mx[i][1], mx[i - 1][1]);
				chmax(mx[i][1], a[i - 1].second + d);
			}
		}
		else {
			if (a[i - 1].second == 0) {
				if (d == 0) {
					upd(f[i][1], f[i - 1][1]);
					chmax(mx[i][1], mx[i - 1][1]);
				}
				else {
					upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d - 1) % mod);
					chmax(mx[i][1], mx[i - 1][1]);
					chmax(mx[i][1], a[i - 1].second + d);
				}
				upd(f[i][0], 1LL * f[i - 1][1] * Qpow(2, d - 1) % mod);
				chmax(mx[i][0], mx[i - 1][1]);
				chmax(mx[i][0], a[i - 1].second + (ds + dh) / 2);
			}
			else {
				if (a[i - 1].second - a[i - 1].first == a[i].second - a[i].first) {
					upd(f[i][1], f[i - 1][1]);
					chmax(mx[i][1], mx[i - 1][1]);
					chmax(mx[i][1], a[i].second);
				}
				else {
					upd(f[i][0], f[i - 1][1]);
					chmax(mx[i][0], mx[i - 1][1]);
					chmax(mx[i][0], a[i - 1].second + (ds + dh) / 2);
				}
				if (a[i - 1].second - a[i].first == a[i].second - a[i - 1].first) {
					upd(f[i][0], f[i - 1][0]);
					chmax(mx[i][0], mx[i - 1][0]);
				}
				if (d >= 0) {
					upd(f[i][1], 1LL * f[i - 1][1] * Qpow(2, d) % mod);
					chmax(mx[i][1], mx[i - 1][1]);
					chmax(mx[i][1], a[i - 1].second + d);
					upd(f[i][0], 1LL * f[i - 1][1] * (Qpow(2, d) - 1) % mod);
					if (d > 0) {
						chmax(mx[i][0], mx[i - 1][1]);
						chmax(mx[i][0], a[i - 1].second + (ds + dh) / 2);
					}
					if (d == 0) upd(f[i][1], f[i - 1][0]);
					else upd(f[i][1], 1LL * f[i - 1][0] * Qpow(2, d - 1) % mod);
					chmax(mx[i][1], mx[i - 1][0]);
					chmax(mx[i][1], d);
					upd(f[i][0], 1LL * f[i - 1][0] * Qpow(2, d - 1) % mod);
					chmax(mx[i][0], mx[i - 1][0]);
					chmax(mx[i][0], (a[i].second + a[i].first - x0) / 2);
				}
			}
		}
	}
	cout << (f[m][1] % mod + mod) % mod << ' ' << mx[m][1] << endl;
	return 0;
}

[NOI 2015] 寿司晚宴

题意

将 $ 2 $ 至 $ n $ 的正整数划分为三个集合 $ A $ , $ B $ , $ C $ ,使得 $ \forall a \in A, b \in B, gcd(a,b) = 1 $ ,求方案数,对一个读入的 $ p $ 取模输出。

数据范围: $ n≤500,p≤1e9 $

题解

注意到一个性质:一个数 $ n $ 只会有一个大于等于 $ \sqrt{n} $ 的质因子,而在本题中不大于 $ \sqrt n $ 的质因子不超过 $ 8 $ 个。

一个思路是暴力搜出这 $ 8 $ 个质因子归属于谁,然后对于大于含有一个 $ \sqrt n $ 的质因子的数根据这个质因子分类计算。但是我操作一下之后总是会有重复计算的情况。

考虑状压 $ DP $ 。如果只有 $ ≤22 $ 的数(即最大质因子为那 $ 8 $ 个),可以 $ f_{i,j,k} $ 表示考虑到前 $ i $ 个数, $ A $ 集合中包含的质因子集合为 $ j $ , $ B $ 集合中包含质因子集合为 $ k $ 的方案数。显然这里要求 $ j \cap k = \complement $

对于含有至少一个 $ ≥23 $ 的质因子的数,我们把它们按照这个质因子排序,这个质因子相同的一起处理。设 $ g_{0/1,i,j,k} $ 表示把这个质因子分给 $ A/B $ 集合, $ A $ 集合中包含的质因子集合为 $ j $ , $ B $ 集合中包含质因子集合为 $ k $ 的方案数。显然这里要求 $ j \cap k = \complement $ 。

但是两个数组都会包含 $ A,B $ 均不包含该质因子的情况,设这段数对应的区间是 $ [l,r] $ ,那么 $ f_{r,j,k} = g_{0,r,j,k}+g_{1,r,j,k}-f_{l-1,j,k} $

总复杂度可以做到 $ O(n * 3^8) $ ,但这里写的是 $ O(n * 4^8) $

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
const int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};

int n, mod;
int f[N][N], g[2][N][N];

struct number {
	int x, p, s;
	bool operator < (const number b) const {
		if (p != b.p) return p < b.p;
		else return x < b.x;
	}
} a[N];

inline void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

int main() {
	cin >> n >> mod;
	for (int i = 1; i < n; ++i) {
		a[i].x = i + 1;
		int y = i + 1;
		for (int j = 0; j < 8; ++j) {
			if (y % pri[j] == 0) a[i].s |= (1 << j);
			while (y % pri[j] == 0) y /= pri[j];
		}
		if (y > 1) a[i].p = y;
	}
	sort(a + 1, a + n);
	f[0][0] = 1;
	for (int i = 1; i < n;) {
		if (a[i].p == 0) {
			int s = a[i].s;
			for (int j = 255; j >= 0; --j) {
				for (int k = 255; k >= 0; --k) {
					if (j & k) continue;
					if ((s & k) == 0) {
						upd(f[j | s][k], f[j][k]);
					}
					if ((s & j) == 0) {
						upd(f[j][k | s], f[j][k]);
					}
				}
			}
			++i;
		}
		else {
			for (int j = 0; j < 256; ++j) {
				for (int k = 0; k < 256; ++k) {
					g[0][j][k] = f[j][k];
					g[1][j][k] = f[j][k];
				}
			}
			int nowp = a[i].p;
			while (a[i].p == nowp) {
				int s = a[i].s;
				for (int j = 255; j >= 0; --j) {
					for (int k = 255; k >= 0; --k) {
						if ((s & k) == 0) {
							upd(g[0][j | s][k], g[0][j][k]);
						}
						if ((s & j) == 0) {
							upd(g[1][j][k | s], g[1][j][k]);
						}
					}
				}
				++i;
			}
			for (int j = 0; j < 256; ++j) {
				for (int k = 0; k < 256; ++k) {
					f[j][k] = (g[0][j][k] + g[1][j][k] - f[j][k]);
					if (f[j][k] >= mod) f[j][k] -= mod;
					if (f[j][k] < 0) f[j][k] += mod;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < 256; ++i) {
		for (int j = 0; j < 256; ++j) {
			upd(ans, f[i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}