Educational Codeforces Round 177 (opens new window)

A - Cloudberry Jam

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        int x; cin >> x;
        cout << x * 2 << '\n';
    }
}

B - Large Array and Segments

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    ll n, k, x; cin >> n >> k >> x;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += a[i];
    ll cnt = (x - 1) / sum;
    ll ans = cnt * n;
    x -= cnt * sum;
    for (int i = n; i >= 1; i--) {
        if (x > a[i]) {
            x -= a[i];
            ans += 1;
        }
        else {
            break;
        }
    }
    cout << max(0ll, n * k - ans) << '\n';
    return;
}

int main() {
    // freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

C - Disappearing Permutation

Question

给出一个长度为 $n$ 的排列 $\{a\}$

每次操作给定一个 $x$，永久得把 $a_x$ 修改成 $0$

每次操作后询问，最多执行几次 $a_i=i$ 才能使 ${a}$ 重新变成一个排列

Solution

把一个 $i$ 看个一个点， $i$ 向 $a_i$ 连边，那么这个图会变成几个连通块

如果一个联通块中的一个 $a_i$ 变成 $0$ 了，那么整个联通块都需要执行 $a_i=i$ 的操作，操作次数就是联通块的大小

用并查集或者其他数据结构都可

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    vector<int> fa(n + 1), siz(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        fa[i] = i; siz[i] = 1;
    }

    function<int(int)> find = [&](int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    };

    function<void(int, int)> merge = [&](int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        if (siz[fx] < siz[fy]) swap(fx, fy);
        fa[fy] = fx;
        siz[fx] += siz[fy];
        siz[fy] = 0;
    };

    for (int i = 1; i <= n; i++) {
        merge(i, a[i]);
    }

    int ans = 0;
    vector<int> b(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        int fx = find(x);
        if (b[fx] == 0) {
            ans += siz[fx];
            b[fx] = 1;
        }
        cout << ans << ' ';
    }
    cout << '\n';
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D - Even String

Question

给定一个数组 $c_i$，询问满足如下条件字符串的方案数：

• 对于任何 $s_i=s_j$，都需要满足：$|i-j|$ 是一个偶数

• 字符 $x$ 在 $s$ 中出现的次数为 $c_x$

• $\sum c_i\le 5\times 10^5$

Solution

先不考虑第一个条件，那么这个就是一个经典的组合数学问题，答案就是

$\frac{A_n^n}{A_{c_1}^{c_1}\times A_{c_2}^{c_2}\times \cdots\times A_{c_{26}}^{c_{26}}}$

再考虑加上第二个条件，一种简单的想法是分奇偶，分出那些字母是在奇数位置的，哪些是在偶数位置的，然后使用上面那个公式算出即可，但是这样的时间复杂度是 $O(2^{26}\times 26)$ 会超时

观察到 $\sum c_i\le 5\times 10^5$，考虑能不能像背包问题那样，对于一个字母，考虑放在奇数位置还是偶数位置

所以定义动态规划：$f[i][odd\_sum]$ 表示，前 $i$ 个字母，奇数位的和为 $odd\_sum$ 的方案数

前 $i$ 个字母的数字个数总和为 $pre\_sum$，那么偶数位置的和也可以被唯一确定是 $pre\_sum-odd\_sum$，就不用定义在状态里面了

考虑转移：

• 如果放在奇数位置

前一个状态：$f[i-1][odd\_sum-c_i]=\frac{A_{odd\_sum-c_i}^{odd\_sum-c_i}}{\textstyle \prod_{i\in \text{之前被选中在奇数位}}A_i}$

观察和当前状态之间的关系，可以得到递推关系

$f[i-1][odd\_sum-c_i]\times \frac{A_{odd\_sum}^{odd\_sum}}{A_{odd\_sum-c_i}^{odd\_sum-c_i}\times A_{c_i}^{c_i}}=\frac{A_{odd\_sum-c_i}^{odd\_sum-c_i}}{\textstyle \prod_{i\in \text{之前被选中在奇数位}}A_i}\times \frac{A_{odd\_sum}^{odd\_sum}}{A_{odd\_sum-c_i}^{odd\_sum-c_i}\times A_{c_i}^{c_i}}\rightarrow f[i][odd\_sum]$

• 如果放在偶数位置

也同理：

$f[i-1][odd\_sum]\times \frac{A_{even\_sum}^{even\_sum}}{A_{even\_sum-c_i}^{even\_sum-c_i}\times A_{c_i}^{c_i}}\rightarrow f[i][odd\_sum]$

其中：$even\_sum=pre\_sum-odd\_sum$

考虑答案：

设 $sum=\sum c_i$

• 如果 $sum$ 为偶数，答案就是 $f[26][sum/2]$
• 如果 $sum$ 为奇数，答案就是 $f[26][\lfloor sum/2\rfloor+1]$

最后把第一维改成滚动数组就可以通过了

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr int MAXN = 5e5 + 5;
using ll = long long;
constexpr ll MOD = 998244353;

ll Fac[MAXN], Inv[MAXN];

ll fast_pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init() {
    Fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        Fac[i] = Fac[i - 1] * i % MOD;
    Inv[MAXN - 1] = fast_pow(Fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--)
        Inv[i] = Inv[i + 1] * (i + 1) % MOD;
}


ll F[2][MAXN];

void solve() {
    vector<int> c(27);
    ll sum = 0;
    for (int i = 1; i <= 26; i++)
        cin >> c[i], sum += c[i];
    
    ll pre_sum = 0; // 前 i 的和
    F[0][0] = 1;
    for (int i = 1; i <= 26; i++) {
        for (int j = 0; j <= sum; j++)
            F[i & 1][j] = 0;

        if (c[i] == 0) {
            for (int j = 0; j <= sum; j++)
                F[i & 1][j] = F[1 - i & 1][j];
            continue;
        }
        pre_sum += c[i];

        for (ll odd_sum = pre_sum; odd_sum >= 0; odd_sum --) {
            ll even_sum = pre_sum - odd_sum;
            if (odd_sum >= c[i]) { // 加到奇数里面
                ll now = F[1 - i & 1][odd_sum - c[i]] * Inv[odd_sum - c[i]] % MOD * Fac[odd_sum] % MOD * Inv[c[i]] % MOD;
                F[i & 1][odd_sum] = (F[i & 1][odd_sum] + now) % MOD;
            }
            if (even_sum >= c[i]) { // 加到偶数里面
                ll now = F[1 - i & 1][odd_sum] * Inv[even_sum - c[i]] % MOD * Fac[even_sum] % MOD * Inv[c[i]] % MOD;
                F[i & 1][odd_sum] = (F[i & 1][odd_sum] + now) % MOD;
            }
        }
    }
    ll ans = 0;
    if (sum % 2 == 0) {
        ans = F[26 & 1][sum / 2];
    }
    else {
        ans = F[26 & 1][sum / 2 + 1];
    }
    cout << ans << '\n';
}

signed main() {
    // freopen ("D.in", "r", stdin);
    init();
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}