A – Convert to Ones

压缩之后算有多少个 \(01\) 对，然后找小的代价乘上再加上取反的代价即可。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200;

int n, x, y, cnt;
char str[MAX_N];

int main()
{
    scanf("%d%d%d%s", &n, &x, &y, str + 1);
    str[0] = '1';
    for (int i = 1; i <= n; i++)
        cnt += (str[i] == '0' && str[i - 1] == '1');
    long long ans = 0;
    if (cnt == 0)
        ans = 0;
    else
        ans = 1LL * (cnt - 1) * min(x, y) + y;
    printf("%lld\n", ans);
    return 0;
}

B – Roman Digits

打表，发现从 \(11\) 项之后差值恒为 \(49\)。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200, series[12] = {0, 4, 10, 20, 35, 56, 83, 116, 155, 198, 244, 292};

int main()
{
    int n;
    scanf("%d", &n);
    if (n <= 11)
        printf("%d\n", series[n]);
    else
        printf("%lld\n", series[11] + 1LL * (n - 11) * 49);
    return 0;
}

C – Sky Full of Stars

这道题就比较有意思了。

考虑用容斥来算。正常来讲我们算「至少有 \(i\) 行，\(j\) 列」的时候会得到：

\[ {n \choose i} {n \choose j} f(i, j) \]

其中 \(f(i, j)\) 是剩下乱放的方案数。然而，这种计算方式自身就会发生重复，所以我们容斥的时候并不是把「至少转恰好」这一类删掉，而是自身重复的部分、且在不同的 \(i, j\) 时也会重复出现同样多次的部分进行容斥。系数很简单就是一个 \(-1\)。

那么，我们可以开始正常做容斥：

\[ ans = \sum_{i = 0}^n \sum_{j = 0}^n (-1)^{i + j + 1} {n \choose i} {n \choose j} [i + j > 0] f(i, j) \]

考虑 \(f(i, j)\) 的取值。如果 \(i > 0, j > 0\)，那么很好得出是 \( 3^{(n – i)(n – j)} \times 3 \)。如果有一维为 \(0\)，那么其实选法就变成了 \(3^i 3^{n^2 – ni}\)。带入得到：

\[ ans = \sum_{i = 1}^n \sum_{j = 1}^n (-1)^{i + j + 1} {n \choose i} {n \choose j} 3^{(n – i)(n – j)} + 2\sum_{i = 1}^n (-1)^{i + 1} {n \choose i} 3^i 3^{n^2 – ni} \]

后面那一部分很好用 \(\Theta(n \log n)\) 的时间进行计算，关键是前面那一项，怎么看都是 \(\Theta(n^2)\)。我们把一些东西拆出来、并且分组到最顶级的和式中：

\[ \begin{aligned} part &= \sum_{i = 1}^n \sum_{j = 1}^n (-1)^{i + j + 1} {n \choose i} {n \choose j} 3^{(n – i)(n – j)} \\ &= (-1) \sum_{i = 1}^n (-1)^i {n \choose i} \sum_{j = 1}^n (-1)^j {n \choose j} 3^{n^2 – in – jn + ij} \\ &= (-1) 3^{n^2} \sum_{i = 1}^n (-1)^i {n \choose i} 3^{-in} \sum_{j = 1}^n (-1)^j {n \choose j} 3^{(i – n)j} \end{aligned} \]

后面 \(\sum_{j = 1}^n\) 的部分可以直接二项式合并：

\[ \begin{aligned} part &= (-1) 3^{n^2} \sum_{i = 1}^n (-1)^i {n \choose i} 3^{-in} \sum_{j = 1}^n (-1)^j {n \choose j} 3^{(i – n)j} \\ &= (-1) 3^{n^2} \sum_{i = 1}^n (-1)^i {n \choose i} 3^{-in} [ (1 – 3^{i – n})^n – 1] \end{aligned} \]

搞定了。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200, mod = 998244353;

int n, fac[MAX_N], fac_inv[MAX_N], inv[MAX_N];

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int binomial(int n_, int k_) { return 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod; }

int main()
{
    scanf("%d", &n);
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = 1LL * inv[mod % i] * (mod - mod / i) % mod;
    for (int i = fac[0] = fac_inv[0] = 1; i <= n; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod, fac_inv[i] = 1LL * fac_inv[i - 1] * inv[i] % mod;
    int ans = 0;
    for (int i = 1, opt = 1; i <= n; i++, opt = mod - opt)
        ans = (0LL + ans + 1LL * opt * binomial(n, i) % mod * fpow(3, i) % mod * fpow(3, 1LL * n * (n - i) % (mod - 1)) % mod) % mod;
    ans = 2LL * ans % mod;
    int part = 0;
    for (int i = 1, opt = mod - 1; i <= n; i++, opt = mod - opt)
    {
        int tmpi = 1LL * opt * binomial(n, i) % mod * fpow(3, ((mod - 1) - 1LL * n * i % (mod - 1)) % (mod - 1)) % mod;
        int tmpj = (0LL + fpow((1 + mod - fpow(3, (i + mod - 1 - n) % (mod - 1))) % mod, n) + mod - 1) % mod;
        part = (0LL + part + 1LL * tmpi * tmpj % mod) % mod;
    }
    part = 1LL * part * 3LL % mod * fpow(3, 1LL * n * n % (mod - 1)) % mod * (mod - 1) % mod;
    printf("%lld\n", (0LL + part + ans) % mod);
    return 0;
}