Codeforces Round #738 (Div. 2)

CF 上蓝祭。

\(A\)

看错题后发现可以用无限次与运算。

显然与的越多，结果只会单调不升，而每相邻两个操作一次就可以达到全都与一遍。

那么 \(Ans=a_1\&a_2\&\cdots\&a_n\)。

\(B\)

发现 \(R,B\) 交错填写一定是最优的，唯一需要讨论的是起始位置，根据第一个有颜色的格子讨论即可。

\(C\)

每个经过点恰好一次，简单分类讨论即可。

\(D1\&D2\)

给定两个点一一对应的森林，连边可能不同，要求在两个图均仍为森林的前提下，加尽量多的边。

\(D1\) 的范围可以支持 \(O(n^2)\) 的算法，那么只需要枚举所有可能连边。能连就连。

这个贪心的正确性不难证明，因为每条边的贡献都是一，而且顺序无关。

对于 \(D2\) 则要求使用更高级的方法模拟上述过程。

可以利用 set 记录 \(1\) 中每个连通块与 \(2\) 中的哪些连通块对应，然后考虑 \(1\) 所有中的连通块。

每次连边相当于是合并两个 \(1\) 中的连通块和两个 \(2\) 中的连通块，不失一般性，假设 \(1\) 的连通块数量 \(<\) \(2\) 的。

如果存在 \(>1\) 个元素的行 set，那么它一定可以和任意一个连通块合并。

否则，因为 \(1\) 的连通块个数 \(<\) \(2\) 的，且每个连通块都只对应一个 \(2\) 的连通块，所以每个 \(1\) 对应的都不同。

那么同样可以任取两个合并，直接使用启发式合并，删除 + 合并即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;

const int N = 1e5 + 10;
int n, m[2], fa[2][N];
set<int> s[2][N];
set<int>::iterator it;
set<pair<int, int> > sub; 
map<int, int> mp[N];
vector<pair<int, int> > ans;

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

int Get(int t, int x){
	if(fa[t][x] == x) return x;
	return fa[t][x] = Get(t, fa[t][x]);
}

void Merge(int t, int x, int y){
	for(it = s[t][y].begin(); it != s[t][y].end(); it ++){
		int a = * it;
		s[t][x].insert(a);
		s[t ^ 1][a].erase(y);
		s[t ^ 1][a].insert(x);
		if(!t)
			mp[x][a] = mp[y][a];
		else
			mp[a][x] = mp[a][y];
	}
}

int main(){
	n = read(), m[0] = read(), m[1] = read();
	for(int i = 1; i <= n; i ++) fa[0][i] = fa[1][i] = i;
	for(int t = 0; t < 2; t ++)
		for(int i = 1; i <= m[t]; i ++){
			int u = read(), v = read();
			fa[t][Get(t, u)] = Get(t, v);
		}
	if(m[0] < m[1]) swap(fa[0], fa[1]);
	
	for(int i = 1; i <= n; i ++){
		int u = Get(0, i), v = Get(1, i);
		s[0][u].insert(v);
		s[1][v].insert(u);
		mp[u][v] = i;
	}
	for(int i = 1; i <= n; i ++)
		if(fa[0][i] == i) sub.insert(make_pair(- s[0][i].size(), i));
	
	while(sub.size() > 1){
		int x = sub.begin() -> second; sub.erase(sub.begin());
		int y = sub.begin() -> second; sub.erase(sub.begin());
		if(s[0][x].size() < s[0][y].size()) swap(x, y);
		int a = * s[0][x].begin();
		int b = * s[0][y].begin();
		if(a == b){it = s[0][x].begin(); it ++; a = * it;}
		ans.push_back(make_pair(mp[x][a], mp[y][b]));
		if(s[1][a].size() < s[1][b].size()) swap(a, b);
		Merge(0, x, y);
		Merge(1, a, b);
		sub.insert(make_pair(- s[0][x].size(), x));
	}
	
	printf("%d\n", ans.size());
	for(int i = 0; i < (int) ans.size(); i ++)
		printf("%d %d\n", ans[i].first, ans[i].second);
	return 0;
}

\(E\)

要求构造长度为 \(n\) 的序列，要求：

1. \(L_i\leq a_i\leq R_i\)
2. \(\sum a_i\leq M\)
3. \(\gcd(a_1,a_2,\dots,a_n)=1\)

求方案数。

莫比乌斯反演，设 \(g(a_1,a_2,\dots,a_n)\) 为真当且仅当它满足前两个条件。

\[Ans=\sum\limits_{a_1=L_1}^{R_1}\sum\limits_{\cdots}\sum\limits_{a_n=L_n}^{R_n}[\gcd(a_1,a_2,\dots,a_n)=1]g(a_1,a_2,\dots,a_n) \]

\[=\sum\limits_{a_1=L_1}^{R_1}\sum\limits_{\cdots}\sum\limits_{a_n=L_n}^{R_n}g(a_1,a_2,\dots,a_n)\sum\limits_{d|\gcd(a_1,a_2,\dots,a_n)} \mu(d) \]

\[=\sum\limits_{d=1}^m\mu(d)\sum\limits_{a_1=\lfloor \frac{L_1}{d}\rfloor}^{\lceil\frac{R_1}{d}\rceil}\sum\limits_{\cdots}\sum\limits_{a_1=\lfloor \frac{L_n}{d}\rfloor}^{\lceil\frac{R_n}{d}\rceil}g(a_1d,a_2d,\dots,a_nd) \]

后面的东东可以通过前缀和优化 DP 做到 \(O(nM/d)\) 计算。

总时间复杂度 \(O(nM\log M)\)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
typedef long long LL;
const int N = 1e5 + 10;
const LL P = 998244353;
 
int n, m, tot, l[55], r[55], prm[N];
LL mu[N], f[N], sum[N];
bool vis[N];
 
int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}
 
LL Get(int d){
	int M = m / d;
	f[0] = 1;
	for(int i = 1; i <= M; i ++) f[i] = 0;
	for(int i = 1; i <= n; i ++){
		int L = (l[i] + d - 1) / d, R = r[i] / d;
		if(L > R) return 0;
		for(int j = 0; j <= M; j ++) sum[j] = (f[j] + (j ? sum[j - 1] : 0)) % P;
		for(int j = 0; j <= M; j ++)
			f[j] = ((j - L >= 0 ? sum[j - L] : 0) - (j - R - 1 >= 0 ? sum[j - R - 1] : 0) + P) % P;
	}
	LL sum = 0;
	for(int i = 1; i <= M; i ++) sum = (sum + f[i]) % P;
	return sum;
} 
 
int main(){
	n = read(), m = read();
	for(int i = 1; i <= n; i ++) l[i] = read(), r[i] = read();
	mu[1] = 1;
	for(int i = 2; i <= m; i ++){
		if(!vis[i]) prm[++ tot] = i, mu[i] = P - 1;
		for(int j = 1; j <= tot && prm[j] * i <= m; j ++){
			vis[prm[j] * i] = true;
			if(i % prm[j]) mu[i * prm[j]] = (P - mu[i]);
			else break;
		}
	}
	LL ans = 0;
	for(int i = 1; i <= m; i ++) ans = (ans + mu[i] * Get(i)) % P;
	printf("%lld\n", ans);
	return 0;
}