Codeforces Round #757(Div.2)

这场 $C$ 没有推出来，掉大分了TAT。

C. Divan and bitwise operations

题意

已知序列长度为 $n$ ，定义序列舒适度 $coziness$ 为序列所有子集的异或和的总和。给出 $m$ 个区间 $[l ,r]$ ，以及这个区间的或值，现在求出满足区间限制的序列的任意一个可能的舒适度 $coziness$ 。

分析

首先因为区间一定是合法的，那么对于区间，如果它的或值为 $x$，我们可以让其中一个元素为 $x$ ,其他都为 $0$ 。那么问题就变成了，求给定的若干个 $x$ 和若干个 $0$ （数量相加为 $n$）组成的序列的舒适度。

利用数学公式 $2^{n-1} \times v$ 。其中 $v$ 为所有值的或值 。

简单推导一下。

由于位运算对每个位都是独立的，考虑分别对每一个位求解。

对于某一个位 $bit$ ，一共有 $n$ 个数字，假设有 $a$ 个 $1$ ，$b$ 个 $0$ 。

那么我们要对结果（所有异或和的总和）产生贡献，就要选出若干个数字使得它们异或和为 $1$ 。

那么我们 $1$ 要选择奇数个，而 $0$ 可以选任意个。

选奇数个 $1$ 的方案为 $C_a^1 + C_a^3 + C_a^5 \ldots = 2^{a-1}$ ，对于每个 $0$ 有可以选或不选，有 $2^b$ 个方案。

根据乘法原理，总方案数为 $2^{a-1} \times 2^b = 2^{n-1}$ ，在 $bit$ 位上每次贡献为 $1<<bit$ 。

所以对于每个位，只要有 $1$ ，那么这个位对结果的贡献就是 $2^{n-1} \times (1<<bit)$ 。

假设 $bit$ 位存在 $1$ ，那么 $v$ 中就可以拆除一块 $(1<<bit)$ ，我们按这种方法把 $v$ 拆成若干个块，每个块都能产生这么多贡献，因此可以直接用 $v$ 乘上 $2^{n-1}$ 得到答案。

void solve ()
{
    int n, k, v = 0; cin >> n >> k;
    for (int i = 1, l, r, x; i <= k && cin >> l >> r >> x; i ++ ) v |= x;
    int jc = 1;
    rep(i, 1, n - 1) jc = 1ll * jc * 2 % mod;
    cout << 1ll * jc * v % mod << endl;
}

D1. Divan and Kostomuksha (easy version)

题意

对于给定序列，任意打乱其顺序，问：
$$ \sum_{i=1}^{n} gcd(a_1, a_2, \ldots a_i) $$
的最大值为多少。其中 $1 \le a_i \le 2 \times 10^5$ 。

分析

%%%%% dls，下面的题解是dls的代码。

序列的 $gcd$ 一定是递减的。

设 $cnt(i)$ 表示以 $i$ 为因数的数字的数量，$dp(i)$ 表示以 $i$ 为最大 $gcd$ 的答案。

转移方程：$dp(j) = max(dp(j), cnt(j) \times (j-i) + dp(i))$ 。

这个方程的意义是，选择 $cnt(j)$ 个数字放到最前面，那么产生的 $gcd$ 贡献是 $cnt(j) \times j$ 。

那么对于后一段填不了 $j$ 倍数的位置，不能产生 $j$ 的贡献。

后一段的贡献怎么算呢？可以枚举 $j$ 的因数（因为后面的数如果不是 $j$ 的因数，同时也不是 $j$ 的倍数，产生的贡献为 $1$ ，这等价于填 $1$ ，而 $1$ 也是 $j$ 的因数）。

对于 $j$ 的因子 $i$ ，由于 $dp(i)$ 算的是整个序列的答案，那么后一段也包含进去了，但是前一段会有重复计算，产生贡献为 $i * cnt(j)$ （ $gcd$ 为 $i$ ，一共 $cnt(j)$ 个数字），要减去这个贡献。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5000010;

// cnt(i) 表示以i为因子的数量，dp(i) 表示以i作为最大gcd的答案
ll cnt[N], dp[N];

void solve ()
{
    int n; cin >> n;
    for (int i = 1, x; i <= n && scanf("%d", &x); i ++ ) ++ cnt[x];
    // 找出所有倍数的数量
    for (int i = 1; i < N; i ++ )
        for (int j = i + i; j < N; j += i)
            cnt[i] += cnt[j];
    dp[1] = cnt[1];
    ll ans = 0;
    for (int i = 1; i < N; i ++ )
    {
        for (int j = i + i; j < N; j += i)
            dp[j] = max(dp[j], (ll)cnt[j] * (j - i) + dp[i]);
        ans = max(ans, dp[i]);
    }
    printf("%lld\n", ans);
}

signed main ()
{
    solve();
    return 0;
}

D2. Divan and Kostomuksha (hard version)

题意

如上， $a_i$ 的范围从 $2 \times 10^5$ 变为 $2 \times 10^7$ 。

分析

easy version 的复杂度为 $N log N$ ，瓶颈在于求 $cnt$ 和 $dp$ 。

对于 $dp(4)$ 而言，它可以从 $dp(1)$ 和 $dp(2)$ 转移过来，但是从 $dp(2)$ 转移明显更优，因为它是由 $dp(1)$ 转移过来的。

对于 $dp(i \times j)$ ，如果 $i | j$ ，那么从 $dp(j)$ 转移过来一定比 $dp(i)$ 转移更优，所以我们只需要求 $dp(p1), dp(p2), dp(p3)$ 从哪个转移更优即可， $p_i$ 表示 $i \times j$ 的质因子。

然后我们这样优化后发现 $cnt$ 也只需要算出某个数字的质数倍数字的数量，因此这里也可以优化。

注意 $cnt$ 的枚举顺序。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 20000010;

// cnt(i) 表示i的所有质数倍数的数量，dp(i) 表示以i作为最大gcd的答案
ll cnt[N], dp[N];
int prime[N / 10], cntp;
bool st[N];

void get_prime (int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) prime[cntp ++ ] = i;
        for (int j = 0; i * prime[j] <= n; j ++ )
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

void solve ()
{
    get_prime(N - 1);
    int n; cin >> n;
    for (int i = 1, x; i <= n && cin >> x; i ++ ) ++ cnt[x];
    // 找出所有倍数的数量
    for (int j = 0; j < cntp; j ++ )
        for (int i = (N - 1) / prime[j]; i >= 1; i -- )
            cnt[i] += cnt[i * prime[j]];
    dp[1] = cnt[1];
    ll ans = 0;
    for (int i = 1; i < N; i ++ )
    {
        for (int j = 0; j < cntp && (ll)i * prime[j] < N; j ++ )
        {
            int ij = i * prime[j];
            dp[ij] = max(dp[ij], (ll)cnt[ij] * (ij - i) + dp[i]);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}

signed main ()
{
    solve();
    return 0;
}