P1

51nod 1850 抽卡大赛
基本和直播讲的一样，实现$2$个函数，加入和删除。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int A, G, P, i;
}a[220][220];
const int mod = 1000000007;
int n;
bool operator<(const Node &a, const Node &b) {
    return a.A < b.A;
}
vector<Node> b;
int m[220];
long long f[220];
int p[220];
int v[220];
int z[220];
int inv(int x) {
    return x == 1 ? 1 : (long long)(mod - mod / x) * inv(mod % x) % mod;
}
void del(int x) {
    int invx = inv((mod + 1 - x) % mod);
    for (int i = 1; i <= n; i++) {
        f[i] = (f[i] - f[i - 1] * x % mod + mod) * invx % mod;
    }
}
void add(int x) {
    for (int i = n; i > 0; i--) {
        f[i] = (f[i] * (mod + 1 - x) + f[i - 1] * x) % mod;
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &m[i]);
        int Q = 0;
        for (int j = 0; j < m[i]; j++) {
            scanf("%d%d%d", &a[i][j].A, &a[i][j].G, &a[i][j].P);
            a[i][j].G = (long long)(100 - a[i][j].G) * inv(100) % mod;
            Q += a[i][j].P;
            a[i][j].i = i;
        }
        Q = inv(Q);
        for (int j = 0; j < m[i]; j++) {
            a[i][j].P = (long long)a[i][j].P * Q % mod;
            b.push_back(a[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    sort(b.begin(), b.end());
    f[1] = 1;
    for (int i = 0; i < b.size(); i++) {
        del(p[b[i].i]);
        for (int j = 0; j < n; j++) {
            z[b[i].i] = (z[b[i].i] + f[n - j] * v[j] % mod * b[i].G % mod * b[i].P) % mod;
        }
        p[b[i].i] = (p[b[i].i] + b[i].P) % mod;
        add(p[b[i].i]);
    }
    for (int i = 0; i < n; i++) {
        printf("%d\n", z[i]);
    }
    return 0;
}

P2

51nod 1984 异或约数和
基本和直播讲的一样。

#include <bits/stdc++.h>
using namespace std;
long long S(long long n) {
    long long re = 0;
    for (long long i = n / 4 * 4; i < n; i++) {
        re ^= i;
    }
    return re;
}
int main() {
    long long n, ans = 0;
    cin >> n;
    for (long long i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i);
        if ((n / i) & 1) {
            ans ^= S(j + 1) ^ S(i);
        }
    }
    cout << ans << endl;
}

P3

51nod 2014 小朋友的笑话
基本和直播讲的不一样。
去偷师了一个可持久化线段树复制子树的代码。

#include <bits/stdc++.h>
using namespace std;
int n, m, tt;
int rt[100020];
int s[5000020];
int lc[5000020];
int rc[5000020];
int build(int l, int r) {
    int now = ++tt;
    s[now] = r - l + 1;
    if (l == r) {
        return now;
    }
    int mid = (l + r) / 2;
    lc[now] = build(l, mid);
    rc[now] = build(mid+1, r);
    return now;
}
int query(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return s[x];
    }
    if (r < L || R < l) {
        return 0;
    }
    int mid = (l + r) / 2;
    return query(lc[x], l, mid, L, R) + query(rc[x], mid + 1, r, L, R);
}
int change(int x, int y, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return y;
    }
    if (r < L || R < l) {
        return x;
    }
    int now = ++tt;
    int mid = (l + r) / 2;
    lc[now] = change(lc[x], lc[y], l, mid, L, R);
    rc[now] = change(rc[x], rc[y], mid + 1, r, L, R);
    s[now] = s[lc[now]] + s[rc[now]];
    return now;
}
int main() {
    scanf("%d%d", &n, &m);
    rt[0] = build(1, n);
    for (int i = 1; i <= 100000; i++) {
        rt[i] = rt[0];
    }
    rt[0] = 0;
    for (int i = 0; i < m; i++) {
        int o, l, r, k;
        scanf("%d", &o);
        if (o == 1) {
            scanf("%d%d%d", &l, &k, &r);
            l -= r;
            r = l + 2 * r;
            l = max(l, 1);
            r = min(r, n);
            rt[0] = change(rt[0], rt[k], 1, n, l, r);
            rt[k] = change(rt[k], 0, 1, n, l, r);
        } else {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(rt[0], 1, n, l, r));
        }
    }
    return 0;
}