VP 2020 ICPC 济南

The 2020 ICPC Asia Jinan Regional Contest
Date 2025/10/09
Solved 6 / 13

A	B	C	D	E	F	G	H	I	J	K	L	M
O		O	O			O			Ø		O	O

A - Matrix Equation

现在给定 01 方阵 $A,B$。求满足

$$
A \times C = B \odot C
$$

的 01 方阵 $C$ 的个数。答案对 $998244353$ 取模。

其中 $\odot$ 表示 Hadamard Product

$N \le 200$

把 $C$ 按列拆分：设 $c^{(j)}$ 表示 $C$ 的第 $j$ 列（长度 $N$ 的 0/1 向量），$b^{(j)}$ 为 $B$ 的第 $j$ 列。
等式按列写为：

$$
Ac^{(j)} = \operatorname{diag}(b^{(j)})c^{(j)}\qquad(\text{在 } \mathbb{F}_2 \text{ 上})
$$

因为右侧逐元素乘以 $b^{(j)}$ 对 0/1 向量是线性变换（在 $\mathbb{F}_2$ 中，乘 0/1 是线性的）。
移到一边：

$$
\big(A + \operatorname{diag}(b^{(j)})\big)c^{(j)} = 0 \quad\ (\bmod 2)
$$

记

$$
M_j = A + \operatorname{diag}(b^{(j)}),
$$

其中加法为按位异或（模 2）。
于是第 $j$ 列的可行解空间是线性方程组 $M_j c^{(j)}=0$ 的零空间，其解数为

$$
2^{N - \operatorname{rank}_{\mathbb{F}_2}(M_j)}.
$$

各列彼此独立，因此总答案为

$$
\prod_{j=1}^{N} 2^{N - \operatorname{rank}(M_j)} \bmod\ 998244353.
$$

用 bitset 加速高斯消元，时间复杂度 $O(N \frac{N^3}{w})$

void solve() {
    int n = read();
    using bs = bitset<205>;

    vector<bs> A(n), B(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x = read();
            if (x) A[i].set(j);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x = read();
            if (x) B[i].set(j);
        }
    }

    auto rank_gf2 = [&](auto M) -> int {
        int r = 0;
        for (int c = 0; c < n and r < n; c++) {
            int piv = -1;
            for (int i = r; i < n; i++) if (M[i][c]) { piv = i; break; }
            if (piv == -1) continue;
            swap(M[r], M[piv]);
            for (int i = 0; i < n; i++) if (i != r and M[i][c]) M[i] ^= M[r];
            ++r;
        }
        return r;
    };

    int sum = 0;
    for (int j = 0; j < n; j++) {
        auto M = A;
        for (int i = 0; i < n; i++) {
            if (B[i][j]) M[i].flip(i);
        }
        int r = rank_gf2(M);
        sum += n - r;
    }
    Z ans = power(Z(2), sum);
    cout << ans << "\n";
}

L - Bit Sequence

统计 $x\in[0,L]$ 使得连续 $m$ 个数 $x,x+1,\dots,x+m-1$ 的 1 的个数奇偶性（即 popcount 的奇偶）恰好等于给定序列 $a_0\dots a_{m-1}$

$m \le 100, L \le 10^{18}, T \le 1000$

由于 $m \le 100 \le 128$，枚举 $x$ 低 7 位，枚举跟在低 7 位后面的一段 1 的奇偶性

这样的话，讨论下是否进位，就能知道 $f(x + i)$ 的奇偶性

提前数位 dp 一下方案数，即可 $O(128 \cdot 2 \cdot m)$ 统计答案

时间复杂度 $O(60 \cdot 2 \cdot 2 \cdot 2 + T \cdot 128 \cdot 2 \cdot m)$

int dp[61][2][2][2];

void solve() {
    int m = read(), L = read();

    vector<int> a(m);
    for (auto &x : a) x = read();

    memset(dp, 0, sizeof dp);

    dp[60][0][0][0] = 1;
    for (int i = 59; i >= 7; i--) {
        int w = (L >> i & 1);

        for (int o : {0, 1}) {
            for (int l : {0, 1}) {
                for (int x : {0, 1}) {
                    if (!dp[i + 1][o][l][x]) continue;

                    for (int y = 0; y < (o | w) + 1; y++) {
                        int no = o | (y < w);
                        int nl = y == 0 ? 0 : l ^ 1;
                        int nx = x ^ y;
                        dp[i][no][nl][nx] += dp[i + 1][o][l][x];
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i <= 127; i++) {

        // high xor low = a[0]
        // high = a[0] xor low
        int d = (__builtin_popcount(i) ^ a[0]) & 1;

        for (int l : {0, 1}) {
            int ok = 1;
            for (int j = 1; j < m and ok; j++) {
                int k = i + j;
                if (k & 128) k = 128 * (l ^ 1) + (k & 127);
                int nd = (__builtin_popcount(k) ^ a[j]) & 1;
                ok &= (nd == d);
            }
            if (ok) {
                ans += dp[7][1][l][d];
                if (i <= (L & 127)) ans += dp[7][0][l][d];
            }
        }
    }

    cout << ans << '\n';
}

D - Fight against involution

void solve() {
    int n = read();

    map<int, int> buk;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = read(), r[i] = read();
    }

    vector<int> p(n);
    ranges::iota(p, 0ll);
    ranges::sort(p, [&](int i, int j) {
        if (r[i] != r[j]) return r[i] < r[j];
        return l[i] > l[j];
        // return r[i] < r[j];
    });

    int t = 0, ans = 0;
    for (int i : p) {
        int L = l[i], R = r[i];
        // cerr << L << ' ' << R << '\n';

        if (!buk.count(R)) {
            t = max(t, L);
            buk[R] = t;
        }
        ans += buk[R];
    }
    cout << ans << '\n';
}

C - Stone Game

0 的不用管，1-1 的代价是 1，2-2的代价是 4，1-2的代价是 2 变成 0

那么能 1-2 结合就 1-2 结合变成 0 然后不用管

剩下的就是只有 1 或者只有 2 的情况，拿 2/3 互相转换，来尽量让 1-2 操作变多即可

void solve() {
    int x = read(), y = read(), read();
    int ans = 0;
    while (x >= 3 or y >= 3) {
        int t = min(x, y);
        ans += t * 2;
        x -= t, y -= t;

        // debug(x), debug(y);

        if (y) {
            int t = (y - y / 3) / 2;
            ans += t * 4;
            x += t, y -= t * 2;
        } else {
            int t = (x - x / 3) / 2;
            ans += t;
            y += t, x -= t * 2;
        }
    }

    if (x == 1 and y == 1) ans += 2;
    if (x == 2 and y == 1) ans += 2;
    if (x == 1 and y == 2) ans += 2;
    if (x == 2 and y == 2) ans += 4;

    cout << ans << '\n';
}

G - Xor Transformation

void solve() {
    int x = read(), y = read();

    int t = x ^ y;
    if (t < x) {
        cout << "1\n" << t;
    } else {
        cout << "2\n" << y << " " << x;
    }
}

M - Cook Pancakes!

相当于给定 $2n$ 个整数 $[1, n]$ 和 $[-n, -1]$，每次删 $k$ 个，$x$ 和 $-x$ 不能一起删

void solve() {
    int n = read(), k = read();

    if (k >= n) {
        cout << "2\n";
    } else {
        cout << (2 * n + k - 1) / k << "\n";
    }
}