比赛地址：Dashboard – Codeforces Round #493 (Div. 2) – Codeforces
官方题解：Codeforces Round #493 — Editorial – Codeforces

998A Balloons

题意简述

有$n$袋气球，每袋分别有$a_i$个气球，有两个人，每一袋气球都必须给一个人，且两个人都必须分到气球。求一种分配方案，使得两个人拥有的气球数不一样。无解输出$-1$。
数据范围：$1 \leq n \leq 10, 1 \leq a_i \leq 1000$

思路

显然$n=1$无解，且$n=2, a_1=a_2$也无解。对于其他情况，我们枚举子集搞一搞就好了。复杂度$O(2^n)$。
打的时候写了个只分配一个人一袋其他的给另外一个人的情况，没找到反例，也没fst。复杂度$O(n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 15;

int n, a[MAXN], sum;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        sum += a[i];
    }
    if(n == 1) {
        puts("-1"); return 0;
    }
    if(n == 2 && a[1] == a[2]) {
        puts("-1"); return 0;
    }
    for(int i = 1; i <= n; i++) {
        if(sum - a[i] != a[i]) {
            printf("1\n%d", i);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

998B Cutting

题意简述

给你一个$n$个数的序列$a_i$，要求切若干刀把序列分成若干段，且每一段中奇数和偶数的个数相等。在$x$和$y$两个数之前切一刀的代价是$|x-y|$，要求代价不超过$B$的情况下，最多能切多少刀。
数据范围：$2 \leq n \leq 100, 1 \leq B \leq 100, 1 \leq a_i \leq 100$

思路

首先显然我们可以预处理一个前缀和，$sum[0][i]$表示$a_1$到$a_i$之间有多少偶数，$sum[1][i]$统计奇数。接下来用一个动态规划解决这个问题，令$dp[i][j]$表示在$a_i$和$a_{i+1}$之前切一刀，且切完以后代价限制还剩余$j$的时候最多能切多少刀，可以在前面枚举一个$k$位置，做以下转移
$$ dp[i][j] = \max_{1 \leq k < i} \{ dp[k][j+|a_i-a_{i+1}|]+1 \} \ (sum[0][k] = sum[1][k])$$
而答案可以在所有合法的DP状态中寻找，即
$$ ans = \max_{1 \leq i < n, 0 \leq j \leq B} \{ dp[i][j] \} \ (sum[0][i]=sum[1][i], sum[0][n]-sum[0][i]=sum[1][n]-sum[1][i])$$
直接暴力做转移和统计答案即可，复杂度$O(nB)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 105;

int n, B, a[MAXN], dp[MAXN][MAXN], sum[2][MAXN], ans;

int main() {
    n = readint(); B = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        sum[0][i] += sum[0][i - 1];
        sum[1][i] += sum[1][i - 1];
        sum[a[i] & 1][i]++;
    }
    for(int i = 1; i < n; i++) { // cut at [i, i + 1]
        int cost = std::abs(a[i] - a[i + 1]);
        for(int j = 0; j <= B - cost; j++) {
            for(int k = 0; k < i; k++) {
                if(sum[0][i] - sum[0][k] == sum[1][i] - sum[1][k] && sum[0][k] == sum[1][k]) {
                    dp[i][j] = std::max(dp[i][j], dp[k][j + cost] + 1);
                }
                if(sum[0][n] - sum[0][i] == sum[1][n] - sum[1][i]) {
                    ans = std::max(ans, dp[i][j]);
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

997A Convert to Ones

题意简述

给你一个长度为$n$的01串，你可以对这个串做两种操作：

1. 区间翻转，一次花费$x$
2. 区间取反，一次花费$y$

求把这个串变为全1串的最小代价。
数据范围：$1 \leq n \leq 300 000, 0 \leq x, y \leq 10^9$

思路

可以观察到我们一定有两种可能的最优方案，如果原串中包含$a$段连续的全0段，一种是通过$a-1$次翻转把0的部分翻转到一起，再进行$1$次取反；另一种是直接原地进行$a$次取反。除此以外，没有更优方案。因此，我们只需要讨论$x$和$y$的大小关系，就可以$O(1)$地求出答案，除了$a=0$的情况无需花费任何代价。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 300005;

int n;
LL x, y, ans;
char s[MAXN];

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

997B Roman Digits

题意简述

求可以用满足$x+y+p+q=n$的$x, y, p, q$以$x+5y+10p+50q$形式表示的正整数$a$的数量。
数据范围：$1 \leq n \leq 10^9$

思路

思路的表述基于原题面，题意简述有点简单过头了2333
我们考虑一个问题，既然要往$n$个格子里填I、V、X、L四种符号，我们不如把每个符号代表的值-1计算，就是填入的数字变为了$\{ 0, 4, 9, 49 \}$。
我们考虑只有$\{ 0, 4, 9 \}$的情况，显然，当填入了9个4的时候，可以用4个9去替换它，剩下的空位就填入0，这样就构造出了一种统计重复的情况。为了避免重复，我们可以从0到$\min(8, n)$枚举4的个数，剩下的位置填入0或9的所有方案数加和即是去过重后的方案数。
现在我们的集合中加入了49，问题变得复杂了一些。我们依然研究可能产生重复的情况，我们想要求这样的一些数对$(i, j)$，使得$4i+9j$表示出来的数加减若干个49后会与另外一个数对$(i’, j’)$表示的数重复。这样的情况，我们只需要统计$i+j$的最小值，在其他空位上填0或49，就可以不重不漏地统计了。实际上这个我们可以理解为在模49意义下做统计。显然，这里的$i, j < 49$。
对于每个模49后的值，维护得到这个值的最小$i+j$值$a_i$，答案就是$\sum_{i=0}^{48} (n-a_i+1)$。
复杂度$O(49^2)$。
诶等一下，打了个表发现$n=12$以后的答案是等差数列，公差49，我们得到了优秀的$O(1)$打表做法。
其实你对着上面的正统做法看一眼，就知道为什么公差是49了2333

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 55;

int n, mn[MAXN];

int main() {
    n = readint();
    memset(mn, 0x3f, sizeof(mn));
    for(int i = 0; i < 49; i++) {
        for(int j = 0; j < 49; j++) {
            mn[(4 * i + 9 * j) % 49] = std::min(mn[(4 * i + 9 * j) % 49], i + j);
        }
    }
    LL ans = 0;
    for(int i = 0; i < 49; i++) {
        ans += std::max(0, n - mn[i] + 1);
    }
    printf("%lld", ans);
    return 0;
}

997C Sky Full of Stars

题意简述

给你一个$n \times n$的矩阵，每个格子有三种颜色可以填，求存在一行或者一列填入了同种颜色的矩阵填色方案数。输出答案对$998244353$取模后的值。
数据范围：$1 \leq n \leq 1 000 000$

思路

如果我们已知$f(i, j)$表示有i行和j列被染上同种颜色的方案数，那么答案可以用经典容斥计算，即
$$ ans = \sum_{0 \leq i \leq n, 0 \leq j \leq n, i+j>0} \binom{n}{i} \binom{n}{j} (-1)^{i+j+1} f(i, j) $$
我们接下来讨论一下怎么求$f(i, j)$。
我们发现，当$i, j$中一个为0的时候，情况比较好办，例如，$f(0, k)=3^k \cdot 3^{n(n-k)}$，选中的$k$列每一列指定一种颜色，其他格子XJB填就好。
而更普遍的情况是$i, j$都不为0的情况，由于行列中间有交点，此时同种颜色的行列的颜色一定相同，即$f(i, j)=3 \cdot 3^{(n-i)(n-j)}$。
解决了$f(i, j)$的问题后，我们发现，直接暴力求值复杂度会是$O(n^2)$以上的，不好处理，我们需要优化。
对于$i, j$中一个为0的情况，我们不妨暴力统计，这部分的复杂度是$O(n \log n)$的。
另外一部分写出来是这样的
$$ \sum_{i=1}^n \sum_{j=1}^n \binom{n}{i} \binom{n}{j} (-1)^{i+j+1} 3 \cdot 3^{(n-i)(n-j)} $$
换个元先，$i \rightarrow n-i, j \rightarrow n-j$
$$ \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \binom{n}{n-i} \binom{n}{n-j} (-1)^{2n-i-j+1} 3^{ij+1} $$
我们知道组合数的对称性以及一些关于$-1$的幂次的性质，可以变形如下
$$ \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \binom{n}{i} \binom{n}{j} (-1)^{i+j+1} 3^{ij+1} $$
我们固定$i$来枚举$j$，改变求和顺序
$$ 3 \cdot \sum_{i=0}^{n-1} \binom{n}{i} (-1)^{i+1} \sum_{j=0}^{n-1} \binom{n}{j} (-1)^j 3^{ij} $$
把$-1$和$3$合并一下
$$ 3 \cdot \sum_{i=0}^{n-1} \binom{n}{i} (-1)^{i+1} \sum_{j=0}^{n-1} \binom{n}{j} (-3^i)^j $$
我们知道有二项式定理$(a+b)^n = \sum_{i=0}^n \binom{n}{i} a^i b^{n-i}$，后面对$j$的求和可以构造二项式定理的形式简化成求乘幂
$$ 3 \cdot \sum_{i=0}^{n-1} \binom{n}{i} (-1)^{i+1} \{ [1+(-3^i)]^n – (-3^i)^n \} $$
现在这个式子只需要枚举$i$就可以做求和了，复杂度$O(n \log n)$，只需要对上面两种情况分开求和就可以把复杂度搞成对的了。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1000005, MO = 998244353;

inline LL fpow(LL n, LL k) {
    LL res = 1;
    for(; k; k >>= 1) {
        if(k & 1) res = res * n % MO;
        n = n * n % MO;
    }
    return res;
}

LL mul[MAXN], inv[MAXN];

inline void calc() {
    mul[0] = mul[1] = inv[0] = inv[1] = 1;
    for(int i = 2; i < MAXN; i++) {
        mul[i] = mul[i - 1] * i % MO;
    }
    for(int i = 2; i < MAXN; i++) {
        inv[i] = (-(MO / i) * inv[MO % i] % MO + MO) % MO;
    }
    for(int i = 2; i < MAXN; i++) {
        inv[i] = inv[i - 1] * inv[i] % MO;
    }
}

inline LL C(int n, int m) {
    return mul[n] * inv[m] % MO * inv[n - m] % MO;
}

LL n;

int main() {
    calc();
    n = readint();
    LL ans = 0;
    for(int i = 1, j = 1; i <= n; i++, j *= -1) {
        ans = (ans + 2 * C(n, i) * j % MO * fpow(3, i + n * (n - i)) % MO + MO) % MO;
    }
    for(int i = 0, j = -1; i < n; i++, j *= -1) {
        ans = (ans + 3 * C(n, i) * j % MO 
            * (fpow(1 - fpow(3, i), n) - fpow(-fpow(3, i), n)) % MO + MO) % MO;
    }
    ans = (ans % MO + MO) % MO;
    printf("%lld", ans);
    return 0;
}