Codeforces Round 976 (Div. 2)

C. Bitwise Balancing (C)

先求出 \(b - c\) 的值，再考虑 \(a\) 的每个二进制位取0或1对答案的影响。vp的时候不知道为什么错了很多次。

void solve() {
    ll b, c, d;
    scanf("%lld%lld%lld", &b, &c, &d);
    if(b - c > d) {
        printf("-1\n");
        return;
    }
    ll x = d - (b - c), cst = 0;
    for(int r = 0; r < 61; r++) {
        ll y = 1ll << r;
        if((y & b) == 0 && (y & c)) cst |= y;
    }
    x -= cst;
    if(x < 0) {
        printf("-1\n");
        return;
    }
    ll add = 0, sub = 0;
    for(int r = 0; r <= 61; r++) {
        ll y = 1ll << r;
        if((y & b) == 0 && (y & c) == 0) add |= y;
        else if((y & b) && (y & c)) add |= y, sub |= y;
    }
    if((x & add) == x && (x ^ sub) <= (1ll << 61)) printf("%lld\n", x ^ sub);
    else printf("-1\n");
}

D. Connect the Dots (D)

注意到 \(d \leq 10\)，用10个并查集保存连边操作为 \(d_i\) 时的连通情况，同时维护每个并查集的右端点，每次从当前并查集最右侧开始遍历，可避免 \(d_i\) 相同时、对同一个点多次操作导致TLE. 最后合并每层的信息即可。

const int N = 2e5 + 10;
int f[12][N], r[12][N];
int find(int id, int i) {
    if(f[id][i] == i) return i;
    return f[id][i] = find(id, f[id][i]);
}
void merge(int id, int x, int y) {
    int fx = find(id, x), fy = find(id, y);
    f[id][fy] = fx;
    r[id][fx] = max(r[id][fx], r[id][fy]);
}
void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= 10; i++) {
        for(int j = 1; j <= n; j++) {
            r[i][j] = f[i][j] = j;
        }
    }
    while(m--) {
        int a, d, k;
        scanf("%d%d%d", &a, &d, &k);
        if(find(d, a) != find(d, a + d * k)) {
            for(int i = a + d;;) {
                merge(d, a, i);
                if(find(d, a) == find(d, a + d * k)) break;
                int x = r[d][find(d, i)];
                i = x + d;
            }
        }
    }
    for(int i = 1; i <= 10; i++) {
        for(int j = 1; j <= n; j++) {
            int fa = find(i, j);
            if(fa != j) merge(0, j, fa);
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        if(f[0][i] == i) cnt++;
    }
    printf("%d\n", cnt);
}

E. Expected Power (E)

\(f(s)^2 = \sum\limits_{i = 0} ^ 9 \sum\limits_{j = 0} ^ 9 b_ib_j \times 2^{i + j}\)，对每个二进制位，\(b_i\) 和 \(b_j\) 最多有4种不同的组合，维护每位每种情况的概率即可求得期望。

void solve() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    ll b = inv(10000);
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++) {
        int p;
        scanf("%d", &p);
        p1[i] = p * b % mo;
        p0[i] = (1 - p1[i] + mo) % mo;
    }
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            dp[i][j][0][0] = 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 10; j++) {
            for(int k = 0; k < 10; k++) {
                int t1 = (a[i] >> j) & 1, t2 = (a[i] >> k) & 1;
                ll tmp[2][2];
                for(int p : {0, 1}) {
                    for(int q : {0, 1}) {
                        tmp[p][q] = dp[j][k][p][q] * p0[i] % mo + dp[j][k][p ^ t1][q ^ t2] * p1[i] % mo;
                        if(tmp[p][q] >= mo) tmp[p][q] -= mo;
                    }
                }
                for(int p : {0, 1}) {
                    for(int q : {0, 1}) {
                        dp[j][k][p][q] = tmp[p][q];
                    }
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            ans += dp[i][j][1][1] * (1 << i + j) % mo;
            if(ans >= mo) ans -= mo;
        }
    }
    printf("%lld\n", ans);
}

F还没补