CF1614 - Codeforces Round 757 (Div. 2)

比赛链接

C. Divan and bitwise operations

题意

存在一个长度为 $n$ 的正整数序列 $\{a_i\}$，$m$ 个限制条件，每个限制条件由 $l, r, x$ 构成，表示 $\{a_i\}$ 在区间 $[l,r]$ 中的元素或运算值为 $x$。对于任意一个满足该条件的序列，求该序列的所有子序列的异或值之和，结果对 $10^9+7$ 取模。

数据范围：$1\leqslant n, m\leqslant 2\cdot10^5$。

思路

开始自己从每一位 $a_i$ 的取值去想的，结果发现根本无法求出所有子序列的异或值之和，看了题解才发现这题巨妙（

既然不容易求出每个子序列然后进行异或再求和，那就直接考虑异或运算下的子序列对答案的贡献。

考虑二进制位的第 $i$ 位，如果所有的 $x$ 或起来这一位都是 $0$，那么就不存在 $a_j$ 的第 $i$ 为 $1$，

现在考虑存在第 $i$ 位为 $1$ 的 $a_j$，令集合 $A$ 为所有 $a_j$ 第 $i$ 位为 $0$，$B$ 为所有 $a_j$ 第 $i$ 位为 $1$，则 $|A|+|B| = n$，

直接从子序列角度分析，一个子序列可以视为分别从集合 $A$ 和集合 $B$ 中取出元素，按照原有顺序，构成子序列，所以一个子序列的第 $i$ 位异或值为 $1$，当且仅当，它选取了奇数个 $B$ 中的元素，也就是

$$\sum = \binom{|B|}{1}+\binom{|B|}{3}+\cdots+\binom{|B|}{k}$$

如果 $|B|$ 为奇数，则 $k=|B|$，否则 $k=|B|-1$。利用二项式系数的递推式，可以得到

$$\sum = \binom{|B|-1}{0}+\binom{|B|-1}{1}+\binom{|B|-1}{2}+\binom{|B|-1}{3}+\cdots+\binom{|B|-1}{|B|-1} = 2^{|B|-1}$$

于是第 $i$ 位为 $1$ 的子序列个数为

$$2^{|A|} \cdot \sum = 2^{|A|}\cdot 2^{|B|-1}=2^{|A|+|B|-1}=2^{n-1}$$

故，无论 $A,B$ 中元素如何，只要 $B\neq \varnothing$，第 $i$ 位为 $1$ 的子序列的个数都为定值 $2^{n-1}$。

$B\neq \varnothing$ 等价于所有 $x$ 或起来第 $i$ 位为 $1$，那么对所有子序列求和，答案就是

$$2^{n-1}\cdot\mathop{\text{OR}}\limits_{i=1}^mx_i$$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 1e9 + 7;
int ksm(int a, int b) {int ret = 1; while (b) {if (b & 1) ret = ret * a % P; a = a * a % P; b >>= 1;} return ret;}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m, tot = 0;
		cin >> n >> m;
		vi a(m);
		for (int i = 0; i < m; i++) {
			int l, r, x;
			cin >> l >> r >> x;
			tot |= x;
		}
		cout << tot * ksm(2, n-1) % P << '\n';
	}
	return 0;
}

D1. Divan and Kostomuksha (easy version)

题意

给出一个序列 $\{a_i\}$，可以对该序列进行重排，求重排后

$$S_n = \sum_{i=1}^n\text{gcd}(a_1,a_2,\cdots,a_i) =: \sum_{i=1}^n g(i)$$

的最大值。

数据范围：$1\leqslant n\leqslant 10^5, 1\leqslant a_i\leqslant 5\cdot 10^6$

思路

明显是dp问题，但不好想状态，利用 $\text{gcd}$ 具有的单调性，为了便于转移，考虑当前序列最后一个 $g(i)$ 的值为dp变量。

考虑 $f(i)$ 为 $a_1,a_2,\cdots, a_t$ 满足 $\text{gcd}(a_1,a_2,\cdots,a_t)=g(t)=i$ 的序列的 $S_t$ 的最大值。所以每一个 $f(i)$ 会确定至少一个长度为 $t\leqslant n$ 的数列，满足 $g(t) = i$。

令 $c_i$ 为含有因数 $i$ 的 $a_j$ 的个数。

由于每一个 $i$ 可以通过 $i\cdot p$（$p$ 为素数）转移过来（从数列上具体来说，是将因数为 $i$ 的数放在 $f(i\cdot p)$ 已有序列的末尾，重复的数字不变位置），最大值变化即

$$f(i) = \max_{p}f(i\cdot p) + i \cdot(c_i - c_{i\cdot p})$$

$c_i-c_{i\cdot p}$ 是为了避免重复计算相同因数 $i$ 对 $f(i)$ 的贡献（因为在 $f(i\cdot p)$ 中已经计算过了，重复的数位置不变）。

初始化： $f(i) = i\cdot c_i$（将以 $i$ 为因数的数排成一个数列）

先用 $Euler$ 筛预处理素数，便于状态转移时直接使用。

总复杂度：$O(M\log M)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int M = 5e6 + 10;
int cnt[M], t[M], f[M];
vi prim;
bool vis[M];
void Euler(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) prim.pb(i);
		for (int j : prim) {
			int k = i * j;
			if (k > M) break;
			vis[k] = 1;
			if (i % j == 0) break;
		}
	}
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	Euler(5e6);
	//cout << prim.size() << '\n'; // 348513
	int n;
	cin >> n;
	vi a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		t[a[i]]++;
	}
	for (int i = 1; i < M; i++) {
		for (int j = 1; j * i < M; j++) {
			cnt[i] += t[j * i];
		}
	}
	for (int i = 1; i < M; i++) f[i] = cnt[i] * i;
	for (int i = M-1; i >= 1; i--) {
		for (int j : prim) {
			int k = i * j;
			if (k >= M) break;
			f[i] = max(f[i], f[k] + i * (cnt[i] - cnt[k]));
		}
	}
	int ans = 0;
	for (int i = 1; i < M; i++) {
		if (cnt[i] == n) {
			ans = max(ans, f[i]);
		}
	}
	cout << ans << '\n';
	return 0;
}