Codeforces Round #1103(Div.3)

D

题目大意：Dabir 和 Egor 对上次节目带来的名气还不够满意，于是他们决定再办一场电视秀：他们将在一个数组 $a$ 上玩他们最爱的游戏，并选用他们最喜欢的整数 $k$。Dabir 先手。在第一步时，可以从数组中任意选择一个元素并将其移除。记上一步所选元素为 $x$。那么在当前步（除了第一步），玩家必须从数组中选择一个元素 $y$，满足 $0 \leq y - x \leq k$，并将其移除。无法进行操作的玩家判负。但由于这不仅是游戏，而是一场真正的表演赛，Arseniy（人称 MAKAN）——鄂木斯克的头号明星再次被邀请担任嘉宾。作为嘉宾，Arseniy 获得了一个特权：允许他代替 Dabir 进行第一步选择，也就是说，他可以为 Dabir 执行首步。

数据范围：$1 \leq t \leq 10^4$，$1 \leq n, k \leq 2 \times 10^5$，$1 \leq a_i \leq n$，$\sum n \le 2 \times 10^5$。

思路：

 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
using i128 = __int128_t;
void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    map<ll, ll> ma;
    rep(i, 0, n - 1) ma[a[i]]++;
    vector<pll> b;
    for (auto& [x, y] : ma) b.emplace_back(x, y);
    int m = sz(b);
    vl c(m);
    rep(i, 0, m - 1) c[i] = b[i].first;
    set<int> s;
    frep(i, m - 1, 0) {
        int tem = ranges::upper_bound(c, c[i] + k) - c.begin();
        auto x = s.lower_bound(i + 1);
        if (b[i].second % 2 == 0) {
            cout << "YES" << endl;
            return;
        } else {
            if (x != s.end() && (*x) < tem) {
                cout << "YES" << endl;
                return ;
            } else {
                s.insert(i);
            }
        }
    }
    cout << "NO" << endl;
    return;
}

E

题目大意：Arseniy 想让他的朋友 Dabir 和 Egor 开心。为此，他打算分别送给他们一个长度相同的数列。一个数组 $b$ 被称为“好数组”，如果它的元素可以重新排列，使得对于所有 $i > 1$，都有 $b_i - b_{i-1} = 1$ 成立。Arseniy 希望 Dabir 和 Egor 能够用这些数组一起玩。为此，必须满足以下条件： 1. 给定的每一个数组都是好数组。2. 如果你将这两个数组首尾相接拼接在一起，得到的新数组依然是好数组。Arseniy 已经有一个长度为 $n$ 的数组 $a$。他打算从 $a$ 中裁剪出这两个数组，也就是说，从 $a$ 中选出两个长度相同且互不重叠的子段。

数据范围：$(1 \le t \le 1000)$，$(1 \le n \le 6000)$，$(1 \le a_i \le n)$，$\sum n \le 6000$。

思路：

 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
using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    vvl ma(n + 1, vl(n + 1, INT_MAX / 3));
    rep(i, 0, n - 1) {
        vl s(n + 1);
        ll maxx = LLONG_MIN / 3, mixx = LLONG_MAX / 3;
        rep(j, i, n - 1) {
            if (j - i + 1 > n / 2 || s[a[j]]) break;
            maxx = max(maxx, a[j]), mixx = min(mixx, a[j]);
            s[a[j]] = 1;
            if (j - i + 1 <= ans) continue;
            if (maxx - mixx + 1 == j - i + 1) {
                if (mixx - (j - i + 1) >= 1 && ma[mixx - (j - i + 1)][j - i + 1] != INT_MAX / 3 && ma[mixx - (j - i + 1)][j - i + 1] < i)
                    ans = max(ans, 1LL * (j - i + 1));
                if (mixx + 2 * (j - i + 1) - 1 <= n && ma[mixx + (j - i + 1)][j - i + 1] != INT_MAX / 3 &&
                    ma[mixx + (j - i + 1)][j - i + 1] < i)
                    ans = max(ans, 1LL * (j - i + 1));
                ma[mixx][j - i + 1] = min(ma[mixx][j - i + 1], 1LL * j);
            }
        }
    }
    cout << ans << endl;
    return;
}

F1

题目大意：这是该问题的简单版本。唯一的区别是 $x = 1$。Egor 在买完他最喜欢的饮料 “Zola Cero” 回家路上的时候，发现 Saransk 正在举行“最佳数字”的竞选活动。投票站里有 $n$ 个人。每个人都带来了一个数字 $a_i$。当第 $i$ 个选民进入投票间时，他会选择一个候选数字 $p_i$，其必须是 $a_i$ 的约数。设选择后的候选数组成的序列为 $[p_1, p_2, \ldots, p_n]$。所有人投票后，我们得到一组投票数组 $[p_1, p_2, \ldots, p_n]$。

数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 5 \cdot 10^5$，$\sum n \le 10^5$。

思路：

  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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using i128 = __int128_t;
const ll MOD = 1e9 + 7;
constexpr int MX = 5e5 + 105;
int lpf[MX];  // 存储每个数的最小素因子，复杂度O(NloglogN)
auto init = [] {
    for (int i = 2; i < MX; i++) {
        if (lpf[i] == 0) {
            for (int j = i; j < MX; j += i) {
                if (lpf[j] == 0) lpf[j] = i;
            }
        }
    }
    return 0;
}();
// 质因数分解，返回值为pair<素因子，素因子次幂>，复杂度O(logN)
vector<pair<int, int>> cnt(int x) {
    vector<pair<int, int>> res;
    while (x > 1) {
        int p = lpf[x];
        int e = 1;
        for (x /= p; x % p == 0; x /= p) {
            e++;
        }
        res.emplace_back(p, e);
    }
    return res;
}
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init2 = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
    ll n, x;
    cin >> n >> x;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    auto tem = cnt(x);
    map<ll, ll> ma;
    rep(i, 0, n - 1) {
        auto tem2 = cnt(a[i]);
        for (auto& [x, y] : tem2) {
            ma[x] += y;
        }
    }
    ll ans = 1;
    for (auto& [a, b] : ma) {
        if (x % a != 0) {
            ans = mul(ans, b + 1);
        }
    }
    for (auto& [c, b] : tem) {
        vl tem3;
        rep(i, 0, n - 1) {
            auto tem2 = cnt(a[i]);
            auto it = ranges::lower_bound(tem2, make_pair(c, 0));
            if (it == tem2.end() || it->first != c)
                tem3.push_back(0);
            else
                tem3.push_back(it->second);
        }
        ll maxx = *max_element(all(tem3));
        ll tem4 = 0;
        rep(j, 1, maxx) {
            vl dp(b + j + 1);
            dp[0] = 1;
            for (auto& p : tem3) {
                vl ndp(b + j + 1);
                rep(v, 0, b + j) {
                    if (!dp[v]) continue;
                    rep(l, 0, max(0LL, min(1LL * j, p))) {
                        if (l + v > b + j) break;
                        ndp[v + l] = (ndp[v + l] + dp[v]) % MOD;
                    }
                }
                dp.swap(ndp);
            }
            ll temp1 = dp[b + j];
            vl dp2(b + j + 1);
            dp2[0] = 1;
            for (auto& p : tem3) {
                vl ndp2(b + j + 2);
                rep(v, 0, b + j + 1) {
                    if (!dp2[v]) continue;
                    rep(l, 0, max(0LL, min(1LL * j - 1, p))) {
                        if (l + v > j + b) break;
                        ndp2[v + l] = (ndp2[v + l] + dp2[v]) % MOD;
                    }
                }
                dp2.swap(ndp2);
            }
            ll temp2 = dp2[b + j];
            tem4 = (tem4 + temp1 % MOD - temp2 % MOD + MOD) % MOD;
        }
        ans = mul(ans, tem4);
    }
    cout << ans << endl;
    return;
}

F2

题目大意：这是该题目的困难版本。唯一的区别是 $1 \le x \le 5 \cdot 10^5$。在买完他最喜欢的汽水“Zola Cero”回家的路上，Egor看到在 Saransk 正在进行“最佳数字”职位的选举。投票站有 $n$ 个人。每个人都带来了一个数字 $a_i$。当第 $i$ 个人进入投票间时，他们会选择一个候选人，该候选人是 $a_i$ 的一个约数。设他们选择的候选人为 $p_i$。当所有人都投票完后，我们得到了票数数组 $[p_1, p_2, \ldots, p_n]$。

数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 10^5$，$1 \leq x \leq 5 \cdot 10^5$，$1 \leq a_i \leq 5 \cdot 10^5$，$\sum n \le 10^5$。

思路：

  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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using i128 = __int128_t;
const ll MOD = 1e9 + 7;
constexpr int MX = 5e5 + 105;
int lpf[MX];  // 存储每个数的最小素因子，复杂度O(NloglogN)
auto init = [] {
    for (int i = 2; i < MX; i++) {
        if (lpf[i] == 0) {
            for (int j = i; j < MX; j += i) {
                if (lpf[j] == 0) lpf[j] = i;
            }
        }
    }
    return 0;
}();
// 质因数分解，返回值为pair<素因子，素因子次幂>，复杂度O(logN)
vector<pair<int, int>> cnt(int x) {
    vector<pair<int, int>> res;
    while (x > 1) {
        int p = lpf[x];
        int e = 1;
        for (x /= p; x % p == 0; x /= p) {
            e++;
        }
        res.emplace_back(p, e);
    }
    return res;
}
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init2 = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(int n, int m) { return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD; }
void solve() {
    ll n, x;
    cin >> n >> x;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    auto tem = cnt(x);
    map<ll, ll> ma;
    rep(i, 0, n - 1) {
        auto tem2 = cnt(a[i]);
        for (auto& [x, y] : tem2) {
            ma[x] += y;
        }
    }
    ll ans = 1;
    for (auto& [a, b] : ma) {
        if (x % a != 0) {
            ans = mul(ans, b + 1);
        }
    }
    for (auto& [c, b] : tem) {
        vl tem3;
        rep(i, 0, n - 1) {
            auto tem2 = cnt(a[i]);
            auto it = ranges::lower_bound(tem2, make_pair(c, 0));
            if (it == tem2.end() || it->first != c)
                tem3.push_back(0);
            else
                tem3.push_back(it->second);
        }
        ll maxx = *max_element(all(tem3));
        ll tem4 = 0;
        rep(j, 1, maxx) {
            vl dp(b + j + 1);
            dp[0] = 1;
            for (auto& p : tem3) {
                vl ndp(b + j + 1);
                rep(v, 0, b + j) {
                    if (!dp[v]) continue;
                    rep(l, 0, max(0LL, min(1LL * j, p))) {
                        if (l + v > b + j) break;
                        ndp[v + l] = (ndp[v + l] + dp[v]) % MOD;
                    }
                }
                dp.swap(ndp);
            }
            ll temp1 = dp[b + j];
            vl dp2(b + j + 1);
            dp2[0] = 1;
            for (auto& p : tem3) {
                vl ndp2(b + j + 2);
                rep(v, 0, b + j + 1) {
                    if (!dp2[v]) continue;
                    rep(l, 0, max(0LL, min(1LL * j - 1, p))) {
                        if (l + v > j + b) break;
                        ndp2[v + l] = (ndp2[v + l] + dp2[v]) % MOD;
                    }
                }
                dp2.swap(ndp2);
            }
            ll temp2 = dp2[b + j];
            tem4 = (tem4 + temp1 % MOD - temp2 % MOD + MOD) % MOD;
        }
        ans = mul(ans, tem4);
    }
    cout << ans << endl;
    return;
}