Visits: 397

AtCoder Grand Contest 038

01 Matrix

简单构造题。

const int N = 1e3 + 7;
int n, m, a, b;

int main() {
    rd(n, m), rd(a, b);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printc('0' + ((i <= b && j <= a) || (i > b && j > a)));
        printc('\n');
    }
    return 0;
}

Sorting a Segment

首先判断一下有没有排序后不变的区间。

除了这些区间之外，如果两个区间排序后相同，当且仅当这两个区间相邻且左右两侧分别是 $\min$ 和 $\max$。

ST 表 RMQ 一下即可。

const int N = 2e5 + 7;
int n, k, a[N], ans, cnt;
vi p;
bool v[N];

int st[2][N][21];

inline void init(int *a, int n) {
    int w = log2(n);
    for (int i = 1; i <= n; i++)
        st[0][i][0] = st[1][i][0] = a[i];
    for (int i = 1; i <= w; i++)
        for (int l = 1, r = 1 << i; r <= n; l++, r++)
            st[0][l][i] = min(st[0][l][i-1], st[0][l+(1<<(i-1))][i-1]),
            st[1][l][i] = max(st[1][l][i-1], st[1][l+(1<<(i-1))][i-1]);
}

inline int Min(int l, int r) {
    int w = log2(r - l + 1);
    return min(st[0][l][w], st[0][r-(1<<w)+1][w]);
}

inline int Max(int l, int r) {
    int w = log2(r - l + 1);
    return max(st[1][l][w], st[1][r-(1<<w)+1][w]);
}

int main() {
    rd(n, k), rda(a, n);
    init(a, n);
    p.pb(1);
    for (int i = 2; i <= n; i++)
        if (a[i] < a[i-1]) p.pb(i), v[i] = 1;
    p.pb(n + 1);
    for (ui i = 1; i < p.size(); i++)
        if (p[i] - p[i-1] >= k) ans = 1;
    for (int i = 2; i < k; i++) cnt += v[i];
    for (int l = 1, r = k; r <= n; l++, r++) {
        cnt -= v[l], cnt += v[r];
        if (cnt && (l == 1 || Min(l - 1, r - 1) != a[l-1] || Max(l, r) != a[r])) ++ans;
    }
    print(ans);
    return 0;
}

LCMs

简单数论题，随便莫反一下即可。

namespace shai {
    const int N = 1e6 + 7;
    int p[N], v[N], phi[N], miu[N];

    inline void init(int n) {
        v[1] = phi[1] = miu[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!v[i]) p[++p[0]] = v[i] = i, phi[i] = i - 1, miu[i] = -1;
            for (int j = 1; j <= p[0] && i * p[j] <= n && p[j] <= v[i]; j++)
                v[i*p[j]] = p[j],
                phi[i*p[j]] = phi[i] * (p[j] - 1 + (p[j] == v[i])),
                miu[i*p[j]] = p[j] == v[i] ? 0 : -miu[i];
        }
    }
}
using shai::miu;

const int N = 2e5 + 7, M = 1e6;
int n, a[N], c[M|1];
modint s[M|1], d[M|1], ans;

int main() {
    init(M), shai::init(M);
    rd(n), rda(a, n);
    for (int i = 1; i <= n; i++) ++c[a[i]];
    for (int i = 1; i <= M; i++) {
        for (int j = i; j <= M; j += i)
            d[i] += binom(c[j], 2) * j * j + s[i] * j * c[j],
            s[i] += j * c[j] % P;
    }
    for (int i = 1; i <= M; i++) {
        modint now = 0;
        for (int j = 1; i * j <= M; j++)
            if (miu[j] > 0) now += d[i*j];
            else if (miu[j] < 0) now -= d[i*j];
        ans += now * v[i];
    }
    print(ans);
    return 0;
}

Unique Path

这题有点误导性，最重要的一点是 $(a,b,1) + (b,c,1) \not\to (a,c,1)$。

先考虑所有 $(x,y,0)$ 的条件，则 $x,y$ 在一棵树上，形成的图是一个森林，用并查集可以得到。

这时如果条件 $(x,y,1)$ 中的 $x,y$ 在同一棵树上，则无解。

否则，设森林中树的个数为 $c$。

若不存在 $(x,y,1)$ 的条件，则有解当且仅当 $c – 1 \le m – n + c \le \binom c2$。

若存在 $(x,y,1)$ 的条件，则有解当且仅当 $\max(3,c) \le m – n + c \le \binom c2$。

#define Fail prints("No"), exit(0);
const int N = 1e5 + 7;
int n, m, q, f[N], c;
vector<pi> p;
bool v[N];

int get(int x) {
    return x == f[x] ? x : (f[x] = get(f[x]));
}

int main() {
    rd(n, m, q);
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1, x, y, z; i <= q; i++) {
        rd(x, y, z), ++x, ++y;
        if (!z) f[get(x)] = get(y);
        else p.pb(mp(x, y));
    }
    for (pi o : p)
        if (get(o.fi) == get(o.se)) Fail;
    for (int i = 1; i <= n; i++) c += !v[get(i)], v[get(i)] = 1;
    int k = m - n + c;
    if (!p.size()) prints((c - 1 <= k && k <= 1ll * c * (c - 1) / 2) ? "Yes" : "No");
    else prints((max(3, c) <= k && k <= 1ll * c * (c - 1) / 2) ? "Yes" : "No");
    return 0;
}

Gachapon

题意

• 有一个随机数生成器，每次可以有 $\frac {a_i}{\sum_{i=0}^{n-1}a_i}$ 的概率生成 $i$。
• 求对于每个 $i$，都有 $i$ 被生成了至少 $b_i$ 次的期望时间。
• $n, \sum_{i=0}^{n-1} a_i, \sum_{i=0}^{n-1} b_i\le 400$，答案对 $998244353$ 取模。

题解

设 $\max(S)$ 表示 $S$ 中的元素被生成到规定次数的最大时间，即所有元素都被生成到规定次数的期望时间，则
$$
ans = E(\max(U))
$$
其中 $U$ 是全集，$E$ 表示期望。

根据 Min-Max 容斥，设 $\min(S)$ 表示 $S$ 中的元素被生成到规定次数的最小时间，即至少一个元素被生成到规定次数的期望时间，有
$$
ans = \sum_{S \subseteq U} (-1)^{|S|+1} E(\min(S))
$$
考虑如何计算 $E(\min(S))$，有
$$
E(\min(S)) = \sum_{i \in S, 0 \le x_i < b_i} P(x_i)E(x_i)
$$
其中 $P(x_i)$ 表示状态 $x_i$ 的出现概率，$E(x_i)$ 表示状态 $x_i$ 的期望持续时间。

显然当 $S$ 相同时 $E(x_i)$ 都一样
$$
E(x_i) = \frac A{A_S}
$$
为了方便，不妨认为 $a,b$ 的下标从 $1$ 开始，于是其中的 $A = \sum_{i=1}^{n} a_i$，$A_S = \sum_{i \in S} a_i$。

考虑如何求 $P(x_i)$，即要求 $i \in S$ 的 $i$ 恰好出现 $x_i$ 次的概率，此时不再需要考虑 $U – S$ 中的元素。

设 $X = \sum_{i \in S}x_i$，此时为有标号概率（设 $i,j \in S$，先 $i$ 后 $j$ 和先 $j$ 后 $i$ 是两种情况），因此考虑 EGF，对于 $i$ 的 EGF 为
$$
f_i(x) = \sum_{n \ge 0} \left(\frac {a_i}{A_S}\right)^n \frac{x^n}{n!}
$$
所以
$$
P(x_i) = X! \prod_{i \in S} \left(\frac {a_i}{A_S}\right)^{x_i}\frac 1{x_i!}
$$
整理一下，我们要算的就是这个玩意儿
$$
\begin{aligned}
ans &= E(\max(U)) \\
&= \sum_{S \subseteq U} (-1)^{|S|+1} E(\min(S)) \\
&= \sum_{S \subseteq U} (-1)^{|S|+1} \left(\sum_{i \in S, 0 \le x_i < b_i} P(x_i)E(x_i)\right) \\
&= \sum_{S \subseteq U} (-1)^{|S|+1} \frac A{A_S}\sum_{i \in S, 0 \le x_i < b_i} P(x_i) \\
&= \sum_{S \subseteq U} (-1)^{|S|+1} \frac A{A_S}\sum_{i \in S, 0 \le x_i < b_i} X! \prod_{i \in S} \left(\frac {a_i}{A_S}\right)^{x_i}\frac 1{x_i!} \\
&= A\sum_{S \subseteq U} \sum_{i \in S, 0 \le x_i < b_i}(-1)^{|S|+1} \frac {X!}{A_S^{X+1}} \prod_{i \in S} \frac {a_i^{x_i}}{x_i!} \\
\end{aligned}
$$
考虑一下 $\sum_{S \subseteq U} \sum_{i \in S, 0 \le x_i < b_i}$ 本质上枚举了啥。

其实就是对于每个 $i$，都可以选或者不选，如果选还要考虑选多少个。

于是显然 DP，状态中需要记录 $A_S$ 和 $X$ 的值，因此设 $f_{i,j,k}$ 表示考虑了前 $i$ 个数，$A_S = j$，$X = k$ 的贡献之和。

初始状态为 $f_{0,0,0} = -1$。

转移为
$$
f_{i+1,j,k} \leftarrow f_{i,j,k} \\
f_{i+1,j+a_{i+1},k+l} \leftarrow -(\frac{a_{i+1}^{l}}{l!}f_{i,j,k})(l < b_{i+1})
$$
目标为
$$
ans = A\sum_{j=1}^{A}\sum_{k=0}^B \frac{k!}{j^{k+1}}f_{n,j,k}
$$
其中 $B = \sum_{i=1}^{n}b_i$。

注意到转移类似一个背包，因此倒序枚举 $j$ 可以省掉 $i$ 这一维。

总时间复杂度 $\mathcal O(AB^2)$。

代码

const int N = 407;
int n, a, b, A, B;
modint f[N][N], ans;

int main() {
    init(400);
    rd(n);
    f[0][0] = P - 1;
    for (int i = 0; i < n; i++) {
        rd(a, b);
        for (int j = A; ~j; j--)
            for (int k = B; ~k; k--)
                if (f[j][k].x) {
                    modint o = 1;
                    for (int l = 0; l < b; l++, o *= a)
                        f[j+a][k+l] -= o * vp[l] * f[j][k];
                }
        A += a, B += b;
    }
    for (int j = 1; j <= A; j++) {
        modint o = v[j];
        for (int k = 0; k <= B; k++, o *= v[j])
            if (f[j][k].x)
                ans += p[k] * o * f[j][k];
    }
    print(ans * A);
    return 0;
}

Two Permutations

题意

• 给定两个 $0 \sim n – 1$ 的排列 $p_{0\dots n-1},q_{0\dots n-1}$。
• 构造两个 $0 \sim n – 1$ 的排列 $a_{0\dots n-1}, b_{0\dots n-1}$，使得：
  • $a_i = i$ 或 $a_i = p_i$。
  • $b_i = i$ 或 $b_i = q_i$。
• 要求最大化 $\sum_{i=0}^{n-1} [a_i \ne b_i]$。
• $n \le 10^5$。

题解

考虑最小化 $\sum_{i=0}^{n-1}[a_i=b_i]$。

显然每个循环之间相互独立，环内要么不变，要么转一格。

记 $x_i$ 表示 $i$ 在 $p$ 中的环，$v(x_i)$ 表示这个环是否转。

记 $y_i$ 表示 $i$ 在 $q$ 中的环，$v(y_i)$ 表示这个环是否转。

考虑一个 $i$：

1. 若 $p_i = i$，$q_i = i$，则任何情况下都有贡献。
2. 若 $p_i = i$，$q_i \ne i$，则当 $v(y_i) = 0$ 时有贡献。
3. 若 $p_i \ne i$，$q_i = i$，则当 $v(x_i) = 0$ 时有贡献。
4. 若 $p_i \ne i$，$q_i \ne i$，$p_i = q_i$，则当 $v(x_i) = v(y_i)$ 时有贡献。
5. 若 $p_i \ne i$，$q_i \ne i$，$p_i \ne q_i$，则当 $v(x_i) = v(y_i) = 0$ 时有贡献。

发现这是一个集合划分模型：两个集合 $S,T$，对于一个环 $i$，如果 $v(i) = 0$，则 $i \in S$，否则 $i \in T$。

然而这样并没有办法做，集合划分模型中的约束应为两个物品不在同一个集合。

于是考虑修改一下定义：记 $y_i$ 表示 $i$ 在 $q$ 中的环，$v(y_i)$ 表示这个环是否转。

于是重新考虑一个 $i$：

1. 若 $p_i = i$，$q_i = i$，则任何情况下都有贡献，我们直接扔掉这种情况。
2. 若 $p_i = i$，$q_i \ne i$，则当 $v(y_i) = 1$ 时有贡献，连边 $(S, y_i, 1)$。
3. 若 $p_i \ne i$，$q_i = i$，则当 $v(x_i) = 0$ 时有贡献，连边 $(x_i, T, 1)$。
4. 若 $p_i \ne i$，$q_i \ne i$，$p_i = q_i$，则当 $v(x_i) \ne v(y_i)$ 时有贡献，连边 $(x_i, y_i, 1)$，$(y_i, x_i, 1)$。
5. 若 $p_i \ne i$，$q_i \ne i$，$p_i \ne q_i$，则当 $v(x_i) = 0$，$v(y_i) = 1$ 时有贡献，连边 $(x_i,y_i,1)$。

跑最小割即可。

据说时间复杂度是 $\mathcal O(n \sqrt n)$，理由是连出来的图实际上是一张二分图，且容量均为 $1$。

代码

namespace Dinic {
    const int N = 2e5 + 7, M = 1e6 + 7;
    const ll inf = 1e18;
    int n, S, T, h[N], hi[N], e[M], t[M], tot, d[N];
    ll mxf, f[M];
    inline void add(int x, int y, ll z, int o = 1) {
        e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
        if (o) add(y, x, 0, 0);
    }
    inline bool bfs() {
        for (int i = 1; i <= n; i++) d[i] = 0;
        queue<int> q;
        q.push(S), d[S] = 1;
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (int i = h[x]; i; i = t[i]) {
                int y = e[i];
                ll z = f[i];
                if (d[y] || !z) continue;
                q.push(y), d[y] = d[x] + 1;
                if (y == T) return 1;
            }
        }
        return 0;
    }
    ll dinic(int x, ll nwf) {
        if (x == T) return nwf;
        ll rst = nwf;
        for (int &i = hi[x]; i; i = t[i]) {
            int y = e[i];
            ll z = f[i];
            if (d[y] != d[x] + 1 || !z) continue;
            ll k = dinic(y, min(z, rst));
            if (!k) d[y] = 0;
            else f[i] -= k, f[i^1] += k, rst -= k;
            if (!rst) break;
        }
        return nwf - rst;
    }
    inline void main() {
        while (bfs()) {
            for (int i = 1; i <= n; i++) hi[i] = h[i];
            ll now;
            while ((now = dinic(S, inf))) mxf += now; 
        }
    }
    inline void init(int _n, int _S, int _T) {
        n = _n, S = _S, T = _T, tot = 1, mxf = 0;
        for (int i = 1; i <= n; i++) h[i] = 0;
    }
}

const int N = 1e5 + 7;
int n, p[N], q[N];
int t = 2, S = 1, T = 2, ans;
int x[N], y[N];
bool u[N], v[N];

int main() {
    rd(n), rda(p, n), rda(q, n);
    for (int i = 1; i <= n; i++) ++p[i], ++q[i];
    for (int i = 1; i <= n; i++)
        if (!u[i]) {
            ++t;
            int o = i;
            while (!u[o]) u[o] = 1, x[o] = t, o = p[o];
        }
    for (int i = 1; i <= n; i++)
        if (!v[i]) {
            ++t;
            int o = i;
            while (!v[o]) v[o] = 1, y[o] = t, o = q[o];
        }
    Dinic::init(t, S, T);
    ans = n;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i && q[i] == i) --ans;
        if (p[i] == i && q[i] != i) Dinic::add(S, y[i], 1);
        if (p[i] != i && q[i] == i) Dinic::add(x[i], T, 1);
        if (p[i] != i && q[i] != i && p[i] == q[i])
            Dinic::add(x[i], y[i], 1), Dinic::add(y[i], x[i], 1);
        if (p[i] != i && q[i] != i && p[i] != q[i])
            Dinic::add(x[i], y[i], 1);
    }
    Dinic::main();
    print(ans - Dinic::mxf);
    return 0;
}