[数据结构与算法]The 2021 ICPC Asia Regionals Online Contest (II)

比赛链接

A. Sort

1. $k=1$ 检查数组是否有序；
2. $k=2$ 相当于再环上找个起点使得数组有序，直接判断；
3. $k\ge 3$ 考虑插入排序，每次暴力找到第 $i$ 小的数的位置 $p_i$ ，构造 $0p_i?1p_{i}n$ 和排列 $132$ 将第 $i$ 小的放到最后面，重复 $n$ 次即可，段数和 $\le 3n$ 满足要求。

$O(n^2)$

#include<bits/stdc++.h>

using namespace std;
const int N = 1e3 + 5;
int n, k, a[N], b[N];
void Solve() {
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
    if (is_sorted(a + 1, a + n + 1))
        return puts("0"), void();
    if (k == 1) return puts("-2"), void();
    if (k == 2) {
        int i = n;
        for (; i; --i) if (a[i - 1] > a[i]) break;
        if (a[n] > a[1] || !is_sorted(a + 1, a + i)) puts("-2");
        else printf("1\n2\n0 %d %d\n2 1\n", i - 1, n);
        return;
    }
    vector<int> v;
    int *c = b + 1;
    sort(b + 1, b + n + 1);
    for (int i = 1, j; i <= n; ++i, ++c) {
        for (j = 1; j <= n - i + 1; ++j) if (a[j] == *c) break;
        if (j == n) continue;
        v.push_back(j);
        for (int t = j; t <= n - i; ++t) a[t] = a[t + 1];
    }
    printf("%d\n", (int) v.size());
    for (auto x: v)
        if (x == 1) printf("2\n0 %d %d\n2 1\n", x, n);
        else printf("3\n0 %d %d %d\n1 3 2\n", x - 1, x, n);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) scanf("%d%d", &n, &k), Solve();
    return 0;
}

先预处理出最初第 $i$ 小的数的位置 $p_i$ ，将 $i$ 挪到最后相当于对所有 $p_j>p_i$ 减 1 ，那么第 $i$ 小的数的真实位置应该为 $p_i?\sum _{j<i}[p_j<p_i]$ 。用树状数组维护顺序对即可。

$O(n\log n)$

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, k, a[N], c[N], p[N];
void mdy(int i, int w) { for (; i <= n; i += i & -i) c[i] += w; }
int qry(int i, int w = 0) { for (; i; i -= i & -i) w += c[i]; return w; }
void Solve() {
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), p[i] = i, c[i] = 0;
    if (is_sorted(a + 1, a + n + 1))
        return puts("0"), void();
    if (k == 1) return puts("-2"), void();
    if (k == 2) {
        int i = n;
        for (; i; --i) if (a[i - 1] > a[i]) break;
        if (a[n] > a[1] || !is_sorted(a + 1, a + i)) puts("-2");
        else printf("1\n2\n0 %d %d\n2 1\n", i - 1, n);
        return;
    }
    vector<int> v;
    sort(p + 1, p + n + 1, [&](int x, int y) { return a[x] < a[y]; });
    for (int i = 1, j; i <= n; ++i) {
        j = p[i] + qry(p[i]);
        if (j == n) continue;
        v.push_back(j), mdy(p[i], -1);
    }
    printf("%d\n", (int) v.size());
    for (auto x: v)
        if (x == 1) printf("2\n0 %d %d\n2 1\n", x, n);
        else printf("3\n0 %d %d %d\n1 3 2\n", x - 1, x, n);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) scanf("%d%d", &n, &k), Solve();
    return 0;
}

B. Mailman

经过的路径总是一条欧拉回路，所以题目可以转化为动态修改某个点度数，并询问将所有点度数变为偶数的最小花费。

由于 $n\le 3$ ，考虑对列建线段树，每个节点维护中间节点度数全为偶数，且左右侧节点度数状态分别为 $S,T$ 的最小花费。

合并的时候 $O(2^{3n})$ 枚举左右和中间的状态，只用横向边连接。

注意当 $L+1=R/mid+1=R$ 的时候，中间连的边会改变左右端点的状态。

修改点度直接递归到叶子暴力修改然后向上合并即可。

$O(2^{3n}(m+q)\log m)$

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
using ll = int64_t;
const ll Inf = 1e18;
const int N = 5e4 + 5;
int k, n, q, a[N][2]; ll b[N][8]; // 3 * 1e9 > int
void cmin(ll &x, ll y) { x > y ? x = y : 0; }
struct Seg {
    ll tr[N << 2][8][8];
#define lc (p << 1)
#define rc (p << 1 | 1)
    void Up(int p, int L, int R) {
        int m = (L + R) >> 1;
        fp(i, 0, k) fp(j, 0, k) tr[p][i][j] = Inf;
        if (L + 1 == R) fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i ^ t][j ^ t], tr[lc][i][i] + b[m][t] + tr[rc][j][j]);
        else if (m + 1 == R) fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i][j ^ t], tr[lc][i][t] + b[m][t] + tr[rc][j][j]);
        else fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i][j], tr[lc][i][t] + b[m][t] + tr[rc][t][j]);
//        int x = m == L ? k : 0, y = m + 1 == R ? k : 0; // Unified, but twice as slow
//        fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i ^ (x & t)][j ^ (y & t)], tr[lc][i][x ? i : t] + b[m][t] + tr[rc][y ? j : t][j]);
    }
    void Build(int p, int L, int R) {
        if (L == R) {
            auto &w = tr[p];
            int x = a[L][0], y = a[L][1];
            fp(i, 0, k) fp(j, 0, k) w[i][j] = Inf;
            if (k == 3) {
                if (L == 1 || L == n) w[3][3] = x, w[0][0] = 0;
                else w[0][0] = x, w[3][3] = 0;
            } else {
                if (L == 1 || L == n)
                    w[7][7] = x + y, w[4][4] = y, w[2][2] = 0, w[1][1] = x;
                else w[0][0] = x + y, w[3][3] = y, w[5][5] = 0, w[6][6] = x;
            }
            return;
        }
        int m = (L + R) >> 1;
        Build(lc, L, m), Build(rc, m + 1, R), Up(p, L, R);
    }
    void mdy(int p, int L,int R, int x,int y){
        if (L == R) {
            static ll w[8];
            x = 1 << (x - 1);
            fp(i, 0, k) w[i ^ x] = tr[p][i][i];
            fp(i, 0, k) tr[p][i][i] = w[i];
            return;
        }
        int m = (L + R) >> 1;
        y <= m ? mdy(lc, L, m, x, y) : mdy(rc, m + 1, R, x, y), Up(p, L, R);
    }
}T;

int main() {
    ll ans = 0;
    scanf("%d%d%d", &k, &n, &q);
    fp(i, 0, k - 2) fp(j, 1, n) scanf("%d", a[j] + i), ans += a[j][i];
    fp(i, 0, k - 1) fp(j, 1, n - 1) scanf("%lld", b[j] + (1 << i)), ans += b[j][1 << i];
    fp(j, 1, n - 1) fp(i, 0, 7) b[j][i] = b[j][i & (i - 1)] + b[j][i & -i];
    k = (1 << k) - 1, T.Build(1, 1, n);
    for (int x1, y1, x2, y2, w; q--;) {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w), ans += w;
        T.mdy(1, 1, n, x1, y1), T.mdy(1, 1, n, x2, y2);
        printf("%lld\n", ans + T.tr[1][0][0]);
    }
    return 0;
}

C. Range Subsequence

考虑如何从 $[l+1,r]$ 的答案求出 $[l,r]$ 的答案。

设 $f(l,r)$ 表示 $[l,r]$ 中以 $a_l$ 开头的最长 Range 子序列长度， $b_i$ 表示 $i$ 所在的块。

则 $an{s}_{l,r}=an{s}_{l+1,r}+f(l,r)?f(n{x}_l,r)$ ，其中 $n{x}_l$ 表示下一个值等于 $a_l$ 的位置。

考虑分块预处理，对于所有 $i$ ，暴力求出 $f_1(i,k)=f(i,k\sqrt{n}),k\ge b_i$ 和 $f_2(i,j)=f(i,i+j)$ ，其中 $i,i+j$ 在同一个块中。

对于每个块 $t$ 维护块内每个数第一次和最后一次出现的位置 $p_{t,x},q_{t,x}$ ，则有
$$f_1(i,k)=f_1(i,k?1)+f_1(p_{k,a_i+f_1(i,k?1)},k)$$
同理若 $l,r$ 不在一个块中，则
$$f(l,r)=f_1(l,b_r?1)+f_2(p_{b_r,a_l+f_1(l,b_r?1)},r)$$
对于从 $[l,r?1]$ 的答案求出 $[l,r]$ ，对称地维护以 $a_r$ 结尾的答案 $g(l,r)$ ，同样也可以得到 $g_1(i,k)=g(k\sqrt{n},i),k<b_i$ 和 $g_2(i,j)=g(i?j,i)$ 。

注意到 $f_1,g_1$ 以及 $f_2,g_2$ 的空间互补，所以可以压缩空间到 $2n\sqrt{n}\approx 241\mathrm{M}\mathrm{B}$ ，所以 $p,q$ 可以直接开成两个 $n\sqrt{n}$ 的桶（因为 $\mathrm{u}\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\_\mathrm{m}\mathrm{a}\mathrm{p}$ 的 $\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}$ 太慢过不了），总空间约 $500\mathrm{M}\mathrm{B}$ 。

$O(n\sqrt{n}+n\sqrt{m})$

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
#define fd(i, a, b) for(int i = (a), _##i = (b) - 1; i > _##i; --i)
using namespace std;
using ll = int64_t;
const int N = 1e5 + 5;
struct qry { int l, r, id; } q[N];
int a[N], b[N], pr[N], nx[N];
vector<int> f1[N], f2[N], f3[N], p1[315], p2[315];
int main() {
    int n, m, B, S, T; ll val = 0;
    scanf("%d%d", &n, &m), B = sqrt(n) + 1, S = n / sqrt(m) + 1, T = n / B + 1;
    vector<int> pos(n); vector<ll> ans(m);
    fp(i, 1, n) scanf("%d", a + i), --a[i];
    fp(i, 0, m - 1) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q, q + m, [&](qry a, qry b) { return a.l / S == b.l / S ? (a.l / S & 1 ? a.r > b.r : a.r < b.r) : a.l < b.l; });
    fp(t, 0, T - 1) {
        int L = t * B + 1, R = min(n, L + B - 1);
        p1[t].assign(n, 0), p2[t] = p1[t];
        fp(i, L, R) {
            auto &f = f2[i];
            pr[i] = pos[a[i]], pos[a[i]] = i, b[i] = t;
            f.assign(R - i + 1, 0), f[0] = 1, p2[t][a[i]] = i;
            fp(j, i + 1, R) f[j - i] = f[j - i - 1] + (a[j] == a[i] + f[j - i - 1]);
            f1[i].assign(T + 1, 0), f1[i][t + 1] = f[R - i];
        }
        fd(i, R, L) {
            auto &f = f3[i];
            f.assign(i - L + 1, 0), f[0] = 1, p1[t][a[i]] = i;
            fd(j, i - 1, L) f[i - j] = f[i - j - 1] + (a[j] == a[i] - f[i - j - 1]);
            f1[i][t] = f[i - L];
            fd(k, b[i] - 1, 0) f1[i][k] = f1[i][k + 1] + (a[i] >= f1[i][k + 1] && p2[k][a[i] - f1[i][k + 1]] ? f3[p2[k][a[i] - f1[i][k + 1]]].back() : 0);
        }
    }
    pos.assign(n, n + 1);
    fd(i, n, 1) {
        nx[i] = pos[a[i]], pos[a[i]] = i;
        fp(k, b[i] + 1, T - 1) f1[i][k + 1] = f1[i][k] + (a[i] + f1[i][k] < n && p1[k][a[i] + f1[i][k]] ? f2[p1[k][a[i] + f1[i][k]]].back() : 0);
    }
    auto f = [&](int L, int R) {
        if (L > R) return 0;
        if (b[L] == b[R]) return f2[L][R - L];
        int w = f1[L][b[R]], nx = a[L] + w, p;
        if (nx < n && (p = p1[b[R]][nx]) && p <= R) w += f2[p][R - p];
        return w;
    };
    auto g = [&](int L, int R) {
        if (L > R) return 0;
        if (b[L] == b[R]) return f3[R][R - L];
        int w = f1[R][b[L] + 1], nx = a[R] - w, p;
        if (nx >= 0 && (p = p2[b[L]][nx]) && p >= L) w += f3[p][p - L];
        return w;
    };
    int L = 1, R = 0;
    fp(i, 0, m - 1) {
        int ql = q[i].l, qr = q[i].r;
        while (L > ql) --L, val += f(L, R) - f(nx[L], R);
        while (R < qr) ++R, val += g(L, R) - g(L, pr[R]);
        while (L < ql) val -= f(L, R) - f(nx[L], R), L++;
        while (R > qr) val -= g(L, R) - g(L, pr[R]), R--;
        ans[q[i].id] = val;
    }
    for (auto w: ans) printf("%lld\n", w);
    return 0;
}

D. Linear Algebra

E. Nearest Point

考虑固定一个点 $i$ ，并以 $i$ 为参考系。

设 $\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{j}(j,\alpha )$ 表示 $j$ 在 $v_{\alpha }=(\cos \alpha ,\sin \alpha )$ 方向上的投影长。

对于任意两个向量 $j,k$ ，存在 4 个临界角度 $\alpha$ 使得 $\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{j}(j,\alpha )=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{j}(k,\alpha )$ ，易证 $v_{\alpha }\perp j+k$ 或 $v_{\alpha }\perp j?k$ （画图理解一下）。

一共有 $O(n^2)$ 个临界角，把 $[?\pi ,\pi )$ 分成了 $O(n^2)$ 段，每一段内 $i$ 的最近点是不变的。所以可以每一段内任取一个角度，算出最近点，并把这一段的概率都算到那个点上即可。

$O(n^4\log n)$

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
using db = double;
const db Pi = acos(-1);
struct Vec {
    int x, y;
    Vec operator+(Vec b) const { return {x + b.x, y + b.y}; }
    Vec operator-(Vec b) const { return {x - b.x, y - b.y}; }
    db v_deg() const { return atan2(x, -y); }
};
int main() {
    int n; scanf("%d", &n);
    vector<db> d, ans(n);
    vector<Vec> a(n), b(n);
    for (auto &p: a) scanf("%d%d", &p.x, &p.y);
    auto Proj = [&](db x, db y, Vec c) { return abs(x * c.x + y * c.y); };
    fp(i, 0, n - 1) {
        ans.assign(n, 0), d = {-Pi, Pi};
        fp(j, 0, n - 1) b[j] = a[j] - a[i];
        fp(j, 0, n - 1) fp(k, j + 1, n - 1)
            d.push_back((b[j] - b[k]).v_deg()), d.push_back((b[j] + b[k]).v_deg());
        for (auto deg: d) d.push_back(deg + (deg < 0 ? Pi : -Pi));
        sort(d.begin(), d.end());
        fp(t, 1, d.size() - 1) {
            if (d[t] - d[t - 1] < 1e-11) continue;
            int k = 0; db L = d[t] - d[t - 1], m = d[t - 1] + L * 0.5, x = cos(m), y = sin(m), mn = 1e18, w;
            fp(j, 0, n - 1) if (j != i && mn - (w = Proj(x, y, b[j])) > 1e-9) mn = w, k = j;
            ans[k] += L;
        }
        fp(j, 0, n - 1) printf("%.9lf%c", i == j ? 0 : ans[j] / Pi * .5, " \n"[j == n - 1]);
    }
    return 0;
}

F. Leapfrog

题目等价于找到一个排列 $p$ ，最大化 $a_{p_n}+\sum _{i=1}^{n?1}{b}_{p_i}{t}_{p_i}^{n?i}$

设 $p^{\prime }$ 为以 $t$ 第一关键字降序， $b$ 第二关键字升序， $a$ 第三关键字升序排序后的排列。

注意到 b ≤ 1 0 4 , t ∈ { 2 , 3 } b\le10^4,t\in\{2,3\} b≤104,t∈{2,3} ，而 $10^4\times 2^{23}<3^{23}$ ，所以 $p^{\prime }$ 与最优排列的前 $n?23$ 项一定相同。

考虑用 $\mathrm{D}\mathrm{P}$ 来求出最后剩下的 $m$ 个物品的最优排列。

设 $f_{i,j,0/1}$ 表示放了 $i$ 个物品，其中有 $j$ 个 $t=2$ 的物品，以及是否有物品放到了最后的最优答案， $x_i/y_i$ 分别表示第 $i$ 个 $t=2/3$ 的物品的位置。

则有
f i , j , 0 = max ? { f i ? 1 , j , 0 + b x i ? j 2 m ? i , f i ? 1 , j ? 1 , 0 + b y j 3 m ? i } f i , j , 1 = max ? { f i ? 1 , j , 1 + b x i ? j 2 m ? i + 1 , f i ? 1 , j ? 1 , 1 + b y j 3 m ? i + 1 , f i ? 1 , j , 0 + a x i ? j , f i ? 1 , j ? 1 , 0 + a y j } \begin{aligned} f_{i,j,0}&=\max\{f_{i-1,j,0}+b_{x_{i-j}}2^{m-i}, f_{i-1,j-1,0}+b_{y_j}3^{m-i}\}\\ f_{i,j,1}&=\max\{f_{i-1,j,1}+b_{x_{i-j}}2^{m-i+1}, f_{i-1,j-1,1}+b_{y_j}3^{m-i+1},f_{i-1,j,0}+a_{x_{i-j}}, f_{i-1,j-1,0}+a_{y_j}\}\\ \end{aligned} fi,j,0?fi,j,1??=max{fi?1,j,0?+bxi?j??2m?i,fi?1,j?1,0?+byj??3m?i}=max{fi?1,j,1?+bxi?j??2m?i+1,fi?1,j?1,1?+byj??3m?i+1,fi?1,j,0?+axi?j??,fi?1,j?1,0?+ayj??}?
$O(n\log n+23^2)$

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
using ll = int64_t;
const int N = 1e5 + 5, P = 998244353;
struct Data { int a, b, t; } p[N];
int n; ll f[24][24][2], p2[N], p3[N];
void cmax(ll &x, ll y) { x < y ? x = y : 0; }
ll dp(vector<Data> &a, vector<Data> &b) {
    int A = a.size(), B = b.size();
    memset(f, 0x80, sizeof f), f[0][0][0] = 0, n = A + B;
    fp(i, 0, n - 1) fp(j, 0, min(i, B)) {
        if (i - j < A) {
            cmax(f[i + 1][j][1], f[i][j][0] + a[i - j].a);
            fp(k, 0, 1) cmax(f[i + 1][j][k], f[i][j][k] + a[i - j].b * p2[n - i - 1 + k]); // + k !!
        }
        if (j == B) continue;
        cmax(f[i + 1][j + 1][1], f[i][j][0] + b[j].a);
        fp(k, 0, 1) cmax(f[i + 1][j + 1][k], f[i][j][k] + b[j].b * p3[n - i - 1 + k]); // + k !!
    }
    return f[n][B][1];
}
void Solve() {
    fp(i, 1, n) scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].t);
    sort(p + 1, p + n + 1, [](Data x, Data y) { return x.t == y.t ? (x.b == y.b ? x.a < y.a : x.b > y.b) : x.t > y.t; });
    ll ans = 0, m = max(0, n - 23); vector<Data>a, b;
    fp(i, 1, m) ans += (ll) p[i].b * (p[i].t == 2 ? p2[n - i] : p3[n - i]) % P;
    fp(i, m + 1, n) p[i].t == 2 ? a.push_back(p[i]) : b.push_back(p[i]);
    printf("%lld\n", (ans + dp(a, b)) % P);
}
int main() {
    p2[0] = p3[0] = 1;
    fp(i, 1, 23) p2[i] = 2 * p2[i - 1], p3[i] = 3 * p3[i - 1];
    fp(i, 24, N - 1) p2[i] = 2 * p2[i - 1] % P, p3[i] = 3 * p3[i - 1] % P;
    int T; scanf("%d", &T);
    while (T--) scanf("%d", &n), Solve();
    return 0;
}

G. Limit

直接泰勒展开，原式可化为
$$x^{?t}\sum _{i=1}^n{a}_i\sum _{j\ge 1}(?1{)}^{j+1}\frac{(b_{i}x{)}^j}{j}=\sum _{j\ge 1}\frac{1}{j}{x}^{j?t}\sum _{i=1}^n(?1{)}^{j+1}{a}_i{b}_i^j$$
算出所有系数，根据极限定义输出答案即可。

$O(tn)$

#include<bits/stdc++.h>

using namespace std;
using ll = int64_t;
int main() {
    int n, t;
    scanf("%d%d", &n, &t);
    if (!t)return printf("0"), 0;
    vector<ll> a(6);
    ll x, y, z, g, b = t;
    for (int i = 0; i < n; ++i) {
        scanf("%lld%lld", &x, &y), z = y;
        for (int j = 1; j < 6; ++j) a[j] += (j & 1 ? 1 : -1) * x * z, z *= y;
    }
    for (int i = 1; i < t; ++i)
        if (a[i]) return printf("infinity"), 0;
    g = __gcd(a[t], b), a[t] /= g, b /= g;
    if (abs(b) == 1) printf("%lld", a[t]);
    else printf("%lld/%d", a[t], b);
    return 0;
}

H. Set

每次随机在 $S$ 中随机选取 $l=?\frac{512}{r}?$ 个数即可。

考虑出错的概率，即存在 $r$ 个集合，这 $r$ 个集合的并至多为 $256$ 个数中的任意 $127$ 个，即
$$p_{\mathrm{E}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{r}}\le \left(\genfrac{}{}{0ex}{}{k}{r}\right)\left(\genfrac{}{}{0ex}{}{256}{127}\right){\left[\frac{\left(\genfrac{}{}{0ex}{}{127}{l}\right)}{\left(\genfrac{}{}{0ex}{}{256}{l}\right)}\right]}^r<3.502\times 10^{?88}$$
完全可以通过。

$O(256k)$

#include<bits/stdc++.h>

using namespace std;
int main() {
    int k, r;
    scanf("%d%d", &k, &r), r = (512 + r - 1) / r;
    while (k--) {
        string s(256, '0');
        for (int i = 0; i < r; ++i) s[rand() & 255] = '1';
        puts(s.c_str());
    }
    return 0;
}

设 I t = { i + ( t ? 1 ) x m o d ?? 256 + 1 ∣ 0 ≤ i < l } I_t=\{i+(t-1)x \mod 256 + 1\mid 0\le i< l\} It?={i+(t?1)xmod256+1∣0≤i<l} ，任选 $r$ 个集合的并集大小最小为 $l+(r?1)x\ge 128$ ，取 $x\ge ?\frac{128?l}{r?1}?$ 即可。

实际上可以求出下界为 $10$ ，所以只需要任选一个 $10\le x\le 246$ 即可。

$O(256k)$

#include<bits/stdc++.h>

using namespace std;
int main() {
    int k, r, y = 0;
    scanf("%d%d", &k, &r), r = (512 + r - 1) / r;
    for (; k--; y += 10) {
    	string s(256, '0');
        for (int i = 0; i < r; ++i) s[(i + y) & 255] = '1';
        puts(s.c_str());
    }
    return 0;
}

I. Discrete Mathematics

J. Leaking Roof

高格子向四周低格子连边跑拓扑排序即可。

$O(n^2)$

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 500 + 5, M = N * N;
using ll = int64_t;
using db = double;
using arr = int[N];
int in[M], a[N][N], id[N][N];
vector<int> G[M];

void ADD(int u, int v) { G[u].push_back(v), ++in[v]; }

int main() {
    int n, m, cnt = 0;
    scanf("%d%d", &n, &m);
    fp(i, 1, n)a[i][0] = a[i][n + 1] = a[0][i] = a[n + 1][i] = 1e9;
    fp(i, 1, n)fp(j, 1, n)scanf("%d", a[i] + j), id[i][j] = ++cnt;
    fp(i, 1, n) fp(j, 1, n) {
        if (a[i][j] > a[i - 1][j]) ADD(id[i][j], id[i - 1][j]);
        if (a[i][j] > a[i + 1][j]) ADD(id[i][j], id[i + 1][j]);
        if (a[i][j] > a[i][j - 1]) ADD(id[i][j], id[i][j - 1]);
        if (a[i][j] > a[i][j + 1]) ADD(id[i][j], id[i][j + 1]);
    }
    queue<int> q;
    vector<db> f(cnt + 1, m);
    fp(i, 1, cnt) if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (!G[u].empty()) f[u] /= G[u].size();
        for (auto v: G[u]) {
            f[v] += f[u];
            if (!--in[v]) q.push(v);
        }
    }
    for (int i = 1; i <= n; ++i, puts(""))
        fp(j, 1, n) a[i][j] ? printf("0 ") : printf("%lf ", f[id[i][j]]);
    return 0;
}

K. Meal

实际上题目相当于每个人从当前没有被选的菜中以 $a_{i,j}$ 的概率选取一道菜。

所以直接记录当前已经打了的菜的集合为 $S$ 的概率 $f(S)$ ，然后直接枚举下一道菜转移即可。

$O(n{2}^n)$

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 21, M = 1 << 20 | 5, P = 998244353;
using ll = int64_t;
using arr = int[N];
vector<int> inv;
int a[N][N];

int main() {
    inv.resize(2005), inv[1] = 1;
    fp(i, 2, 2e3) inv[i] = (ll) (P - P / i) * inv[P % i] % P;
    int n, m;
    scanf("%d", &n), m = (1 << n) - 1;
    fp(i, 0, n - 1) fp(j, 0, n - 1) scanf("%d", a[i] + j);
    vector<int> f(m + 1), g(m + 1), cnt(m + 1);
    f[0] = 1;
    fp(s, 0, m) cnt[s] = __builtin_popcount(s);
    fp(i, 0, n - 1) {
        vector<ll> ans(n);
        g = f, f.assign(m + 1, 0);
        fp(s, 0, m) if (cnt[s] == i) {
            ll sum = 0, val;
            vector<int> vj;
            for (int t = m ^ s; t; t &= t - 1) vj.push_back(__builtin_ctz(t)), sum += a[i][vj.back()];
            sum = inv[sum];
            for (auto j: vj) val = (ll) g[s] * a[i][j] % P * sum % P, f[s | 1 << j] = (f[s | 1 << j] + val) % P, ans[j] += val;
        }
        fp(j, 0, n - 2) printf("%lld ", ans[j] % P);
        printf("%lld%c", ans.back() % P, "\n\0"[i == n - 1]);
    }
    return 0;
}

L. Euler Function

设 $p$ 是质数，根据欧拉函数的性质可得：

1. 当 $p\mid q$ 时，$\phi (pq)=\phi (p)q$
2. 当 $p?q$ 时，$\phi (pq)=\phi (p)(q?1)$

注意到 $w\le 100$ ，最多只有 $25$ 个质数。

考虑线段树，每个节点开一个长度为 $25$ 的 $\mathrm{b}\mathrm{i}\mathrm{t}\mathrm{s}\mathrm{e}\mathrm{t}$ 表示区间内是否所有数都含有这个质因子。

当整个区间的数都含有质因子 $p$ 时，可以直接打上一个乘法标记，没有则向下递归。

由于只有 $25$ 个质数，所以每个节点至多被暴力修改 $25$ 次。

$O(25n+m\log n)$

预处理写得有点长，应该用埃氏筛法。

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 1e5 + 5, A = 101, P = 998244353;
using ll = int64_t;
bitset<A> vis;
int a[N], phi[A], pr[A], id[A];
vector<pair<int, int>> val[A];
bitset<26> G[A];
void sieves() {
    phi[1] = 1;
    fp(i, 2, A - 1) {
        if (!vis[i]) pr[++pr[0]] = i, phi[i] = i - 1, val[i] = {{i, id[i] = pr[0] - 1}}, G[i][pr[0] - 1] = 1;
        for (int j = 1, x, p; j <= pr[0] && (x = i * (p = pr[j])) < A; ++j) {
            vis[x].flip(), val[x] = val[i], G[x] = G[i];
            if (i % pr[j]) phi[x] = phi[i] * (pr[j] - 1), val[x].emplace_back(pr[j], id[p]), G[x][id[p]] = 1;
            else {
                phi[x] = phi[i] * p;
                for (auto &w: val[x])
                    if (w.second == id[p])
                        w.first *= p;
                break;
            }
        }
    }
}
struct Seg {
    int tag[N << 2], tr[N << 2];
    bitset<26> f[N << 2];
#define lc (p << 1)
#define rc (p << 1 | 1)
    void Up(int p) { tr[p] = (tr[lc] + tr[rc]) % P, f[p] = f[lc] & f[rc]; }
    void upd(int p, int w) { tr[p] = (ll) tr[p] * w % P, tag[p] = (ll) tag[p] * w % P; }
    void Down(int p) { int &w = tag[p]; if (w > 1) upd(lc, w), upd(rc, w), w = 1; }
    void Build(int p, int L, int R) {
        tag[p] = 1;
        if (L == R) return f[p] = G[a[L]], tr[p] = phi[a[L]], void();
        int m = (L + R) >> 1;
        Build(lc, L, m), Build(rc, m + 1, R), Up(p);
    }
    void mdy(int p, int L, int R, int a, int b, int x, int i) {
        if (a <= L && R <= b && f[p][i]) return upd(p, x);
        if (L == R) return f[p][i] = 1, tr[p] = (ll) tr[p] * phi[x] % P, void();
        int m = (L + R) >> 1; Down(p);
        if (a <= m) mdy(lc, L, m, a, b, x, i);
        if (b > m) mdy(rc, m + 1, R, a, b, x, i);
        Up(p);
    }
    int qry(int p, int L, int R, int a, int b) {
        if (a <= L && R <= b) return tr[p];
        int m = (L + R) >> 1, w = 0; Down(p);
        if (a <= m) w = qry(lc, L, m, a, b);
        if (b > m) w = (w + qry(rc, m + 1, R, a, b)) % P;
        return w;
    }
} T;

int main() {
    sieves();
    int n, q; scanf("%d%d", &n, &q);
    fp(i, 1, n) scanf("%d", a + i);
    T.Build(1, 1, n);
    for (int op, l, r, w; q--;) {
        scanf("%d%d%d", &op, &l, &r);
        if (!op) {
            scanf("%d", &w);
            for (auto x: val[w])
                T.mdy(1, 1, n, l, r, x.first, x.second);
        } else printf("%d%c", T.qry(1, 1, n, l, r), "\n\0"[!q]);
    }
    return 0;
}

M. Addition

先求出和 $c$ ，若 $c\ge 0$ ，则默认符号位全为 $1$ ，否则令 $c=?c$ 并默认符号位为 $?1$ 。

若当前位为 $1$ 且实际符号位与默认不符，则高位 $+1$ ，即 $2^k=2^{k+1}?2^k$ 。

$O(n)$

#include<bits/stdc++.h>

using namespace std;
using ll = int64_t;

int main() {
    int n; scanf("%d", &n);
    vector<int> sgn(n);
    for (auto &x: sgn)scanf("%d", &x);
    ll a = 0, b = 1;
    for (ll x, i = 0; i < n; ++i) scanf("%lld", &x), a += sgn[i] * (x << i);
    for (ll x, i = 0; i < n; ++i) scanf("%lld", &x), a += sgn[i] * (x << i);
    if (a < 0) b = -1, a = -a;
    for (ll i = 0; i < n; ++i) {
        printf("%d%c", a & 1, " \0"[i == n - 1]);
        a = (a >> 1) + (a & 1 && sgn[i] != b);
    }
    return 0;
}