2022.11.29 杭州集训Day1 考试记录

2022秋 2022杭州集训

---

得分：

T1	T2	T3	Sum
100	50	0	150

T1

考点：容斥，二项式反演，组合数学

用时：$8:30$ to $9:55$

得分：$100pts$

Description

构造一个长度为 $n$ 的排列 $p$，使其满足 $m$ 条限制，每条限制 给出 $x,y$ 要求 $p_x = y$ 或 $p_y = x$
$1\leq n,m \leq 5\times10^5$

Solution

一道组合数学签到题。

构造排列，肯定从置换环的角度思考。

将限制去重后，不妨将 $(x,y)$ 的限制看做一条边。

那么很容易发现，如果一个点的度数 $\geq 3$，一定无解。

那么有解的情况一定是一些不交的环，链，孤立点。

分类讨论一下：

$1^o$ 孤立点：最简单的情况，令：$cnt_2 = \sum[E(i)=\varnothing]$，方案数为 $cnt_2!$

$2^o$ 自环：很多人没考虑到的情况，方案数为 $1$

$3^o$ 多元环，发现只有正着和反着两种情况。

$4^o$ 长度大于 $2$ 的链，与多元环一样，只有正着和反着两种情况，但是会多出来一个点随便选，那么可以把剩下的那个点算到孤立点上去。

$5^o$ 长度为 $2$ 的链（二元环）：最重要的情况，粗略来看与情况 $4$ 一样，实际上有问题，考虑剩下的那个点，由于长度仅为 $2$，所以会将 $(u,v)$ 这个数对在正反统计两次，造成重复。

考虑去重，实际上重复的情况其实就是把条件的或改成与，下面记 $cnt_1$ 为 二元环的数量。

做个恰好的容斥，将答案减去所有恰好有 $i$ 个二元环取到与的答案。

然后根据二项式反演的思想，改恰好为钦定，再把孤立点选上去。

$$Ans = \sum_{i=0}{(-1)^{i}\dbinom{cnt_1}{i}(cnt_1+cnt_2-i)!}$$

暴力做这个即可。

Summary

评价：组合数学好题，考察了对性质的观察与恰好转钦定的容斥直觉，比较签到。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e6 + 5, mod = 998244353;
int n, m;
struct node {
    int v, nex;
}edge[maxn << 1];
unordered_map <int, int> mapp[maxn];
int head[maxn], len, Du[maxn], Vst[maxn], tot, flag, Cnt1, Cnt2, Answer = 1;
int Frac[maxn], Inv[maxn];
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
inline int Ksm(int A, int B) {
    int res = 1;
    while(B) {
        if(B & 1) res = res * A % mod;
        A = A * A % mod, B >>= 1;
    }
    return res;
}
inline void Search(int x, int fa) {
    if(Vst[x]) { flag = 1; return ; }
    Vst[x] = 1, tot++;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        Search(y, x);
    }
}
inline void Ready() {
    Frac[0] = Inv[0] = 1;
    for(register int i = 1; i <= n; ++i) Frac[i] = Frac[i - 1] * i % mod;
    Inv[n] = Ksm(Frac[n], mod - 2);
    for(register int i = n - 1; i >= 1; --i) Inv[i] = Inv[i + 1] * (i + 1) % mod;
}
inline int C(int x, int y) { return Frac[x] * Inv[y] % mod * Inv[x - y] % mod; }
signed main() {
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    n = read(), m = read();
    Ready();
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        if(!mapp[u][v] && !mapp[v][u]) {
            make_map(u, v), make_map(v, u);
            Du[u]++, Du[v]++;
        }
        mapp[u][v] = mapp[v][u] = 1;
    }
    for(register int i = 1; i <= n; ++i)
        if(Du[i] > 2) { printf("0\n"); return 0; }
    for(register int i = 1; i <= n; ++i) {
        if(!Du[i]) Cnt2++;
        else if(!Vst[i]) {
            tot = 0, flag = 0, Search(i, 0);
            if(tot > 2) {
                Answer = (Answer * 2ll) % mod;
                if(!flag) Cnt2++;
            }
            else if(tot == 2) Cnt1++;
        }
    }
    int Sum = 0;
    for(register int i = 0; i <= Cnt1; ++i) {
        int Cnt = C(Cnt1, i) * Ksm(2ll, Cnt1 - i) % mod * Frac[Cnt1 + Cnt2 - i] % mod;
        if(i & 1) Sum = (Sum - Cnt + mod) % mod;
        else Sum = (Sum + Cnt) % mod;
    }
    printf("%lld\n", Answer * Sum % mod);
    return 0;
}

T2

考点：线段树，差分

用时：$10:10$ to $11:30$

得分：$50pts$

Description

给定 $n$ 个数的序列，每个元素由三元组 $(c,w,a)$ 组成。
给定一种操作，每次操作可以选择一段 $c$ 均相同的区间 $[l,r]$ 将此区间的 $a$ 均减掉 $1$
三种询问，共 $m$ 次：
询问 $1$：单点修改：$a_i,w_i$
询问 $2$：区间覆盖 $c$
询问 $3$：求清空区间 $[x,y]$ 的所有 $a$ 值的最小代价
$1\leq n,m \leq 2\times10^5$

Solution

考虑这个操作，明明是区间操作，代价却只跟两个单点有关，这很不好做，我们希望这个代价跟区间中的所有点都挂上钩。

考虑差分，$w_l + w_r = 2w_l + \sum_{i = l + 1}^{r}{delta_i}$

再考虑一个恒等式：$2w_i \geq w_i - w_{i-1}$

所以做一段区间的中间一定比端点优，从左往右依次加点，那么能加到当前段就加到当前段，否则再新开一段，则贡献为：$\min(a_i, a_{i - 1}) \times (w_i - w_{i - 1}) + 2w_i \times \max(0, a_i - a_{i - 1})$

得到 $O(nm)$ 暴力，$50pts$，考场上止步于此。

我们考虑用线段树维护这个东西。

还是没法在考场上想到如何用线段树维护这种复杂的东西。

我们考虑除了 $2$ 操作，这是很好维护的。

这个贡献是分子区间来贡献的，类似最大子段和的做法，维护两端的颜色和区间答案。

在 $\text{PushUp}$ 时我们讨论两段的颜色是否相同，如果相同就把那个区间合并，重新计算贡献。

考虑把 $2$ 操作加上，他是一个区间推平的操作，我们记 $Sum(l,r)$ 表示 区间 $[l,r]$ 被推平后的答案，把这个东西也扔到线段树上维护即可通过，$\text{PushDown}$ 非常容易，忽略不讲。

Summary

一道线段树好题，需要对线段树有比较好的理解。

事实证明我还是不会线段树。

Code

//The Code Is From Dawn
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, q;
long long a[maxn];
int c[maxn];
long long w[maxn];
struct node {
    int l, r;
    long long s;
    int x, y;
    long long ts;
} sum[maxn << 2];
int lazy[maxn << 2];
void pushdown(int l, int r, int rt) {
    int mid = l + r >> 1;
    if (lazy[rt] != 0) {
        sum[rt << 1].l = sum[rt << 1].r = lazy[rt];
        sum[rt << 1 | 1].l = sum[rt << 1 | 1].r = lazy[rt];
        sum[rt << 1].s = sum[rt << 1].ts;
        sum[rt << 1 | 1].s = sum[rt << 1 | 1].ts;
        lazy[rt << 1] = lazy[rt], lazy[rt << 1 | 1] = lazy[rt];
        lazy[rt] = 0;
    }
}
node add(node s1, node s2) {
    node t;
    t.l = s1.l, t.r = s2.r;
    t.s = s1.s + s2.s;
    t.ts = s1.ts + s2.ts - a[s1.y] * w[s1.y] - a[s2.x] * w[s2.x] + max(0ll,
            a[s1.y] - a[s2.x]) * w[s1.y] + max(0ll, a[s2.x] - a[s1.y]) * w[s2.x];
    if (s1.r == s2.l) {
        t.s += max(0ll, a[s1.y] - a[s2.x]) * w[s1.y] + max(a[s2.x] - a[s1.y], 0ll) * w[s2.x];
        t.s -= a[s1.y] * w[s1.y] + a[s2.x] * w[s2.x];
    }
    return t;
}
void build(int l, int r, int rt) {
    sum[rt].x = l, sum[rt].y = r;
    if (l == r)
        return sum[rt].l = sum[rt].r = c[l], sum[rt].ts = sum[rt].s = a[l] * 2 * w[l], void();
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    sum[rt] = add(sum[rt << 1], sum[rt << 1 | 1]);
    sum[rt].x = l, sum[rt].y = r;
}
void update(int l, int r, int rt, int x, int y, int k) {
    if (x <= l && r <= y) {
        sum[rt].l = sum[rt].r = k;
        sum[rt].s = sum[rt].ts;
        lazy[rt] = k;
        return;
    }
    int mid = l + r >> 1;
    pushdown(l, r, rt);
    if (x <= mid)
        update(l, mid, rt << 1, x, y, k);
    if (mid < y)
        update(mid + 1, r, rt << 1 | 1, x, y, k);
    sum[rt] = add(sum[rt << 1], sum[rt << 1 | 1]);
    sum[rt].x = l, sum[rt].y = r;
}
void change(int l, int r, int rt, int x, int k) {
    if (l == r)
        return sum[rt].s = sum[rt].ts = k * a[l] * 2, void();
    int mid = l + r >> 1;
    pushdown(l, r, rt);
    if (x <= mid)
        change(l, mid, rt << 1, x, k);
    else
        change(mid + 1, r, rt << 1 | 1, x, k);
    sum[rt] = add(sum[rt << 1], sum[rt << 1 | 1]);
    sum[rt].x = l, sum[rt].y = r;
}
node query(int l, int r, int rt, int x, int y) {
    if (x <= l && r <= y)
        return sum[rt];
    int mid = l + r >> 1;
    node s;
    pushdown(l, r, rt);
    s.l = s.r = s.s = s.x = s.y = s.ts = 0;
    s.x = l, s.y = r;
    if (x <= mid)
        s = query(l, mid, rt << 1, x, y);
    if (mid < y) {
        if (x <= mid)
            s = add(s, query(mid + 1, r, rt << 1 | 1, x, y));
        else
            s = query(mid + 1, r, rt << 1 | 1, x, y);
    }
    s.x = l, s.y = r;
    return s;
}
signed main() {
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> c[i] >> w[i];
    build(1, n, 1);
    for (int i = 1; i <= q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, v1, v2;
            cin >> x >> v1 >> v2;
            a[x] = v1, w[x] = v2;
            change(1, n, 1, x, v2);
        }
        if (op == 2) {
            int l, r, v;
            cin >> l >> r >> v;
            update(1, n, 1, l, r, v);
        }
        if (op == 3) {
            int l, r;
            cin >> l >> r;
            cout << query(1, n, 1, l, r).s << endl;
        }
    }
    return 0;
}

T3

考点：图上随机游走，高斯消元，哈希，$\text{min-max}$ 容斥，概率生成函数

用时：$11:45$ to $12:30$

得分：$0pts$

Description

给定 $n$ 个字符串 $s_{1\dots n}$ 和一个空串 $T$，每次给 $T$ 随机接入一个字符，求出 $T$ 中出现 $s$ 中所有字符串的期望时间。$n\le 15,\sum|s|\le 10^5$。

Solution

考场上根本没看，一道非常好的题目。

我们先从一些子问题分析起：

$1^o$ 暴力情况：JSOI2009有趣的游戏

求概率版本。

我们把所有模式串扔到一个AC自动机上，那么问题变成了一个图上随机游走。

设计DP：$f[i]$ 表示状态 $i$ 出现的概率，$f[ch[u][i]] = \sum{f[u]\times p_i}$

这个转移显然是有环的，所以要高斯消元，复杂度 $O(n^3m^3)$

$2^o$ 对暴力的优化：SDOI2017硬币游戏

暴力的瓶颈在于方程太多，我们发现有用的状态只有 $n$ 个，我们却用了 $nm$ 个方程算了很多无用的东西。

我们考虑把无用的状态缩到一起，统称为 $S$，这样状态缩减到 $n + 1$，我们若能找到 $n + 1$ 个方程即可在 $O(n^3)$ 的时间解决问题。

我们考虑从无用的状态 $S$ 开始，连续的走了某个字符串 $x_i$，他结束了的概率。

注意：即使连续的走了某个字符串 $x_i$，也不一定在 $x_i$ 结束，有可能在走完之前，就已经在某个 $x_j$ 结束了，这时后面的概率不需要计算。

我们发现，这里存在一个等量关系。

前者是 $S + x_i$ 出现的概率为 $\frac{1}{26^{len_i}}P(S)$

后者是以结束点为角度分类，来表达这个式子。

我们发现提前结束的条件是，$x_j$ 的后缀 $A$ 正好是 $x_i$ 的前缀 $A$，而 $S$ 的一段后缀 $len_j - A$，正好是 $x_j$ 的剩余前缀 $len_j - A$，这样就会在 $x_j$ 提前结束。

也就是说，当 $x_j$ 的后缀 $A$ 等于 $x_i$ 的前缀 $A$，就会造成 $\frac{1}{26^{len_j - A}}P(x_j)$ 的贡献。

所以有：

$$\frac{1}{26^{len_i}}P(S) = \sum_{j\neq i}{\sum_{A|Pre(i,A) = Suf(j,A)}{\frac{1}{26^{len_j - A}}P(x_j)}}$$

这样的方程有 $n$ 个，再加上 $\sum_{i}{P(x_i)} = 1$，得到 $n + 1$ 个方程，可以解决问题。

$3^o$ 期望转概率的套路：CTSC2006歌唱王国

给出一个引理：

第一次出现的期望时间等于所有时间从未出现的概率之和

证明需要用到概率生成函数：

我们定义一个形式幂级数 $A(x)$ ，它为概率生成函数，则它的系数 $a_i = P(X = i)$

他有以下两个性质：

• $A(1)=\sum_{i=0}^\infty P(X=i)=1$

• $E(x) = A'(x)=\sum_{i=0}^\infty iP(X=i)x^{i-1}$

我们设：$F(x)$：表示恰好在 $x$ 的时候停止，$G(x)$ 表示第 $x$ 的时刻还没停止

那么显然有：

$g[i] = f[i + 1] + g[i + 1]$

将它写成生成函数的形式：

$xG(x) + 1 = F(x) + G(x)$

整理一下

$F(x) = (x - 1)G(x) + 1$

求导：

$F'(x) = (x - 1)G'(x) + G(x)$

将 $x = 1$ 代入：

$E(1) = F'(1) = G(x)$

结论得证。

而所有时间从未出现的概率之和就是上面的 $P(S)$

所以：$E(min) = P(S)$，这里 $min$ 表示第一次出现

$4^o$ 套上 $min-max$ 容斥

容易发现，经过上面这么多分析，已经与本题要求的东西很接近了。

我们已经会求第一次出现的期望，而此题要求的是所有都出现的期望。

显然可以套上 $min-max$ 容斥，$E(min)$ 通过高消来求。

复杂度 $O(2^nn^3+n\sum{|s|})$

Summary

一道非常好的题目，用到了很多题目的思想套路，以及再套一个 $\text{min-max}$ 容斥，很值得研究。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 20, maxm = 1e5 + 5, mod = 998244353;
const ull Base = 31;
int n;
int pow26[maxm], len[maxn], flag[maxn], St[maxn], num[maxn][maxn], Val[maxn][maxn];
ull poww[maxm], Sum[maxn][maxm];
char S[maxn][maxm];
inline int Ksm(int A, int B) {
    int res = 1;
    while(B) {
        if(B & 1) res = res * A % mod;
        A = A * A % mod, B >>= 1;
    }
    return res;
}
inline void Ready() {
    pow26[0] = 1ll, poww[0] = 1ull;
    for(register int i = 1; i <= 1e5; ++i) pow26[i] = pow26[i - 1] * 26ll % mod, poww[i] = poww[i - 1] * Base;
}
inline ull Hash(int i, int l, int r) { return (Sum[i][r] - Sum[i][l - 1]) * poww[100000 - r];  }
inline bool Check(int x, int y) {
    if(len[x] < len[y]) return 0;
    ull Cnt = Hash(y, 1, len[y]);
    for(register int i = 1; i <= len[x] - len[y] + 1; ++i)
        if(Cnt == Hash(x, i, i + len[y] - 1)) {
            if(len[x] == len[y]) return x < y;
            else return 1;
        }
    return 0;
}
inline int Calc(int x, int y) {
    int Cnt = 0;
    for(register int i = 1; i <= min(len[x], len[y]); ++i)
        if(Hash(x, 1, i) == Hash(y, len[y] - i + 1, len[y])) Cnt = (Cnt + pow26[i]) % mod;
    return Cnt;
}
inline int Gause(int x) {
    Val[x][x + 1] = 1, Val[x][x] = 0;
    for(register int i = 1; i < x; ++i) Val[i][x] = mod - 1, Val[i][x + 1] = 0;
    for(register int i = 1; i < x; ++i) Val[x][i] = 1;
    for(register int i = 1; i <= x; ++i) {
        int Cnt = i;
        for(register int j = i; j <= x; ++j)
            if(Val[j][i]) { Cnt = j; break; }
        swap(Val[i], Val[Cnt]);
        Cnt = Ksm(Val[i][i], mod - 2);
        for(register int j = i; j <= x + 1; ++j) Val[i][j] = Val[i][j] * Cnt % mod;
        for(register int j = i + 1; j <= x; ++j) {
            Cnt = mod - Val[j][i];
            for(register int k = i; k <= x + 1; ++k) Val[j][k] = (Val[j][k] + Val[i][k] * Cnt % mod) % mod;
        }
    }
    return Val[x][x + 1];
}
inline void Work() {
    int Limit = (1 << n), Answer = 0;
    for(register int i = 1; i < Limit; ++i) {
        int top = 0;
        for(register int j = 1; j <= n; ++j)
            if((i & (1 << j - 1)) && flag[j]) { top = -1; break; }
        if(top == -1) continue;
        for(register int j = 1; j <= n; ++j)
            if(i & (1 << j - 1)) St[++top] = j;
        for(register int j = 1; j <= top; ++j)
            for(register int k = 1; k <= top; ++k) Val[j][k] = num[St[j]][St[k]];
        int Cnt = __builtin_popcount(i);
        if(Cnt & 1) Answer = (Answer + Gause(top + 1)) % mod;
        else Answer = (Answer - Gause(top + 1) + mod) % mod;
    }
    printf("%lld\n", Answer);
}
signed main() {
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);
    n = read(), Ready();
    for(register int i = 1; i <= n; ++i) {
        scanf("%s", S[i] + 1);
        len[i] = strlen(S[i] + 1);
        for(register int j = 1; j <= len[i]; ++j) Sum[i][j] = Sum[i][j - 1] + poww[j] * S[i][j];
    }
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j)
            if(i != j && Check(j, i)) { flag[i] = 1; break; }
    for(register int i = 1; i <= n; ++i)
        for(register int j = 1; j <= n; ++j)
            if(!flag[i] && !flag[j]) num[i][j] = Calc(i, j);
    Work();
    return 0;
}