「考试总结」ZROI-21-CSP7连-DAY7 总结

#T1 字符串

Time Limit: 1s Memory Limit: 512MB

#题意简述

给定长度为 \(n(n\leq10^4)\) 的字符串 \(A_0\) 和长度为 \(m(m\leq10^4)\) 的字符串 \(B_0\)，它们都只包含大小写字母。

对于任意整数 \(i\geq1\)，令 \(A_i\) 是由 \(A_{i−1}\) 与 \(B_{i−1}\) 拼接而成的字符串，\(B_i\) 是由 \(B_{i−1}\) 与 \(A_{i−1}\) 拼接而成的字符串。

有 \(T(T\leq10^4)\) 个询问，每个询问给定 \(x(x\leq10^{15})\)，你需要输出 \(A_{935}\) 中的第 \(x\) 个字符是什么。

#大体思路

因为 \(2^{50}>10^{15}\)，而且不难发现 \(A_i\)/\(B_i\) 的长度是 \(2^{i-1}(n+m)\)，所以我们可以提前预处理出来所有层的长度。可以发现如果当前的 \(x\) 在当前层的 \(k\) 串（\(0\) 是 \(A\)，\(1\) 是 \(B\)），且大于一半的长度，那么在上一层一定是在 \(k\text{ xor }1\) 串，且 \(x\) 减去对应的长度，否则一切不变。

按以上思路硬干就完了，时间复杂度 \(O(935\cdot T)\).

#Code

#define ll long long

const int N = 10010;
const ll LIMIT = 1e15;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, m, T, sum; ll len[N];
char s[2][N];

inline void prework() {
    for (int i = 1; i <= 50; ++ i) {
        len[i] = 1ll << (i - 1);
        if (len[i] > LIMIT) len[i] = LIMIT + 1;
        if (LIMIT / sum < len[i]) len[i] = LIMIT + 1;
        else len[i] = len[i] * sum;
    }
    for (int i = 51; i <= 935; ++ i) len[i] = LIMIT + 1;;
}

int main() {
    read(n), read(m), read(T); sum = n + m;
    scanf("%s%s", s[0] + 1, s[1] + 1); prework();
    while (T --) {
        ll x; read(x); int op = 0, now = 935;
        while (now > 1) {
            if (x > len[now - 1])
              op ^= 1, x -= len[now - 1];
            now --;
        }
        if (op == 1) {if (x > m) x -= m, op ^= 1;}
        else {if (x > n) x -= n, op ^= 1;}
        putchar(s[op][x]); putchar('\n');
    }
    return 0;
}

#T2 区间

Time Limit: 1s Memory Limit: 512MB

#题意简述

现在有 \(n(n\leq10^5)\) 个区间，分别是 \([l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\)，保证 \(1\leq l_i<r_i\leq10^{13}\)。

现在要对区间进行操作，每次操作都可以选择一个整数 \(x\) 作为操作基准，这个操作对所有满足 \(l_i<x<r_i\) 的区间生效。

在这个操作以后，区间 \([l_i,r_i]\) 会变成 \([l_i,x]\) 和 \([x,r_i]\) 。

你可以进行 \(m(m\leq10^{18})\) 次这样的操作，要求在操作以后，区间的数量尽可能的多，你需要给出最多可能的区间数量。多组数据 \(T\leq100\).

#大体思路

显然，产生贡献的情况可以在离散化以后，分成一块一块的。 对于区间所有的左右端点离散以后，一个区间一个区间中的贡献都是相同的，其中端点处的贡 献需要单独考虑，端点出的贡献要去掉包含的区间。 这样就可以用左右端点标记的方式，从前往后扫直接处理出每一个区间的贡献，记录下来以后 排序，从高到低依次去考虑操作就可以。

#Code

#define ll long long
#define int long long

const int N = 200010;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

map <int, int> Map;

struct Node {
    int l, r, x;
    inline Node() {}
    inline Node(int l, int r, int x) : l(l), r(r), x(x) { }
    inline bool operator < (const Node &b) const {return x > b.x;}
} a[N];

int T, n, m, tal;

inline int Solve() {
    int now = 0, lst = -1;
    for (auto p : Map) {
        if (now == 0) {
            now = p.second; lst = p.first;
            continue;
        }
        a[++ tal] = Node(lst, p.first - 1, now);
        lst = p.first; now += p.second;
    }
    sort(a + 1, a + tal + 1);
    int ans = 0;
    for (int i = 1; i <= tal; ++ i) {
        int len = a[i].r - a[i].l + 1;
        if (len > m) {ans += m * a[i].x; break;}
        else {ans += len * a[i].x; m -= len;}
    }
    return ans + n;
}

signed main(){
    read(T);
    for (int i = 1; i <= T; ++ i) {
        read(n); read(m); Map.clear(); tal = 0;
        for (int i = 1; i <= n; ++ i) {
            int l, r; read(l); read(r);
            if (r == l + 1) continue;
            ++ Map[l + 1]; -- Map[r];
        }
        printf("Case #%lld: %lld\n", i, Solve());
    }
    return 0;
}

#T3 构树

Time Limit: 1s Memory Limit: 512MB

#题意简述

给定整数 \(n(n\leq800)\)，设 \(M=\dfrac{n(n−1)}2\)，显然 \(n\) 个点的完全图包含 \(M\) 条边。

现给定一个包含 \(n\) 个点的树 \(T\)，点编号为 \(1,\dots,n\) 边有边权，保证边权是 \([1,M]\) 中互不相同的整数。

你需要在树的基础上添加 \(M−n+1\) 条边，形成一个边有权值的完全图 \(G\)，并且满足：

• \(T\) 是 \(G\) 的一棵最小生成树；
• \(G\) 中所有边的边权是 \([1,M]\) 中互不相同的整数。

请你首先求出符合条件的 \(G\) 的数量，答案对 \(10^9+7\) 取模。

此外，如果存在符合条件的 \(G\)，则你需要再构造出一种这样的 \(G\)。

#大体思路

首先不难发现，当我们将给定的边按边权从小到大逐条加入最初边集为空的图时，显然我们考虑一条按边权从小到大额外加入的边，它必然不应能将当前图中的任意连通块相连，否则给定的树一定不是最小生成树，所以当前权值的额外边只能在连通块内部进行连接，每条边的方案数可以用并查集进行维护，然后求积即可，时间复杂度为 \(O(n^2)\).

下面来考虑构造。考虑最小生成树的性质，对于两个点 \(u,v\)，\(V(u,v)\) 表示它们在最小生成树 \(T\) 上简单路径上的最大边权，\(w(u,v)\) 表示完全图 \(G\) 中边 \((u,v)\) 的边权，那么显然应当有 \(V(u,v)\leq w(u,v)\)，否则一定可以将对应的最大的边换成边 \((u,v)\)，与 \(T\) 是最小生成树矛盾。于是我们可以用树上倍增在 \(\log\) 的时间复杂度内得到任意一条边的最小边权限制，按此限制进行排序，依次赋值即可。时间复杂度 \(O(n^2\log n)\).

PS: 本题 std 可以做到 \(O(n^2)\)，以上思路及 Code 是本人在赛时想到的 sb 做法。

#Code

#define ll long long

const int N = 810;
const int M = 500000;
const ll MOD = 1e9 + 7;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T a, T b) {return a > b ? a : b;}
template <typename T> inline T Min(T a, T b) {return a < b ? a : b;}

struct Edge {
    int u, v, w;
    inline bool operator < (const Edge b) const {return w < b.w;}
} e[N], ne[M];

struct TEdge {int u, v, w, nxt;} te[N];

int n, m, fa[N], siz[N], nowans, c[N][N], ncnt;
int ecnt(1), head[N], dep[N], f[21][N], mx[21][N];

int find(int x) {while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;}

void connect(int u, int v) {
    u = find(u), v = find(v);
    ll tmp = siz[u] * (siz[u] - 1) / 2;
    tmp += siz[v] * (siz[v] - 1) / 2;
    if (siz[u] > siz[v]) swap(u, v);
    fa[u] = v; siz[v] += siz[u]; nowans -= tmp;
    nowans += siz[v] * (siz[v] - 1) / 2;
}

inline void add_edge(int u, int v, int w) {
    te[ecnt].u = u, te[ecnt].v = v, te[ecnt].w = w;
    te[ecnt].nxt = head[u], head[u] = ecnt ++;
}

void dfs(int x, int fa) {
    f[0][x] = fa, dep[x] = dep[fa] + 1;
    for (int i = 1; i <= 20; ++ i)
      f[i][x] = f[i - 1][f[i - 1][x]];
    for (int i = 1; i <= 20; ++ i)
      mx[i][x] = Max(mx[i - 1][x], mx[i - 1][f[i - 1][x]]);
    for (int i = head[x]; i; i = te[i].nxt)
      if (te[i].v != fa) {
          mx[0][te[i].v] = te[i].w; dfs(te[i].v, x);
      }
}

int get_limit(int u, int v) {
    int res = -INF;
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; ~i; -- i)
      if (dep[f[i][u]] >= dep[v])
        res = Max(res, mx[i][u]), u = f[i][u];
    if (u == v) return res;
    for (int i = 20; ~i; -- i)
      if (f[i][u] != f[i][v]) {
          res = Max(res, mx[i][u]), u = f[i][u];
          res = Max(res, mx[i][v]), v = f[i][v];
      }
    res = Max(res, Max(mx[0][u], mx[0][v]));
    return res;
}

int main() {
    read(n); m = (n - 1) * n / 2;
    for (int i = 1; i < n; ++ i) {
        read(e[i].u), read(e[i].v), read(e[i].w);
        add_edge(e[i].u, e[i].v, e[i].w);
        add_edge(e[i].v, e[i].u, e[i].w);
        c[e[i].u][e[i].v] = e[i].w;
        c[e[i].v][e[i].u] = e[i].w;
    }  
    sort(e + 1, e + n); int nowedge = 1;
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    for (int i = 1; i <= n; ++ i) siz[i] = 1;
    ll ans = 1;
    for (int i = 1; i <= m; ++ i) {
        if (nowedge < n && e[nowedge].w == i) {
            connect(e[nowedge].u, e[nowedge].v);
            ++ nowedge; continue;
        }
        (ans *= (nowans - i + 1)) %= MOD;
    }
    printf("%lld\n", ans); nowedge = 1;
    if (!ans) return 0; dfs(1, 0);
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j < i; ++ j)
        if (!c[i][j])  {
            ne[++ ncnt].u = i, ne[ncnt].v = j;
            ne[ncnt].w = get_limit(i, j);
        }
    sort(ne + 1, ne + ncnt + 1); int necnt = 1;
    for (int i = 1; i <= m; ++ i) {
        if (nowedge < n && e[nowedge].w == i) {++ nowedge; continue;}
        c[ne[necnt].u][ne[necnt].v] = i; c[ne[necnt].v][ne[necnt].u] = i; ++ necnt;
    }
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) printf("%d ", c[i][j]);
        printf("\n");
    }
    return 0;
}

#T4 字典树

Time Limit: 1s Memory Limit: 512MB

#题意简述

给定 \(n(n\leq10)\) 个数字串 \(S_1,\dots,S_n\)，每个串的长度都为 \(m(m\leq100)\)。

然而，现在每个字符串内部的字符顺序都可能出现随机的调换，例如若 \(S_i=012\)，那么调换后 \(S_i\) 会等概率随机成为 \(012,021,102,120,201,210\) 中的一种。

现要把调换后的 \(n\) 个数字串全部插入一棵字典树中（调换的结果是等概率随机的），问这个字典树结点数量的期望是多少，答案对 \(998244353\) 取模。

#大体思路

考虑字典树的实际含义：给定字符串集合中的任意一个字符串的任意一个前缀都会对应一个字 典树结点。

因此我们可以枚举字符串 \(T\)，判断 \(T\) 出现在字典树上的概率是多少，也就是 \(T\) 是至少一个给定串的前缀的概率是多少。 设 \(T\) 中包含 \(t_0\) 个 \(0\)，\(t_1\) 个 \(1\)，\(\dots\)，\(t_9\) 个 \(9\)，再设 \(S_x\) 中包含 \(s_0\) 个 \(0\)，\(s_1\) 个 \(1\)，\(\dots\)，\(s_9\) 个 \(9\)，那 么 \(T\) 是 \(S_x\) 前缀的概率应当是： \[ \dfrac{\prod(s_j^{\underline{t_i}})}{(\sum s_i)^{\underline{(\sum t_i)}}} \] 其中 \(x^{\underline m}=x\times(x-1)\times\cdots\times(x-m+1)\).

对这个式子的一个简单说明：分母表示从 \(\sum s_i\) 个数中挑出 \(\sum t_i\) 个数构成一个前缀的方案数， 分子则是对每个位置具体限定其等于 \(T\) 中对应位置的方案数。 设这个概率为 \(p(T, x)\)，那么可知 \(T\) 是至少一个 \(S_x\) 的前缀的概率（记为 \(P(T)\)）为： \[ P(T)=1-\prod\limits_{x=1}^n(1-p(T,x)), \] 而我们要求的答案就是所有 \(P(T)\) 的总和。注意到 \(p(T,x)\) 只与 \(t_0,t_1,\dots,t_9\) 的大小有关，而与怎样排列无关，于是 \(P(T)\) 也可以记为 \(P(t_0,t_1,\dots,t_9)\) 再考虑到构成 \(T\) 的方案数，可知答案为 \[ \sum\limits_{t_0,t_1\dots,t_9}\left(\dfrac{(\sum t_i)!}{\prod(t_i!)}\cdot P(t_0,t_1,\dots,t_9)\right), \] 直接计算的时间复杂度为 \(O(m^{10}\times n)\)，无法接受，注意到 \(n\) 很小，考虑将 \(P(T)\) 进行变幻得到： \[ P(T)=\sum\limits_{\varnothing\ne S\subseteq\{1,2,\dots,n\}}\left((-1)^{|S|-1}\prod\limits_{i\in S}p(T,i)\right), \] 其实就是将原本的连乘的式子展开了，变成了容斥的形式，于是答案变为 \[ \begin{aligned} &\sum\limits_{t_0,t_1\dots,t_9}\left(\dfrac{(\sum t_i)!}{\prod(t_i!)}\cdot P(t_0,t_1,\dots,t_9)\right)\\ =&\sum\limits_{t_0,t_1\dots,t_9}\left(\dfrac{(\sum t_i)!}{\prod(t_i!)}\cdot \sum\limits_{\varnothing\ne S\subseteq\{1,2,\dots,n\}}\left((-1)^{|S|-1}\prod\limits_{i\in S}p(T,i)\right)\right)\\ =&\sum\limits_{\varnothing\ne S\subseteq\{1,2,\dots,n\}}(-1)^{|S|-1}\cdot\left(\sum\limits_{t_0,t_1\dots,t_9}\left(\dfrac{(\sum t_i)!}{\prod(t_i!)}\cdot\prod\limits_{i\in S}p(T,i)\right)\right)\\ =&\sum\limits_{\varnothing\ne S\subseteq\{1,2,\dots,n\}}(-1)^{|S|-1}\cdot\left(\sum\limits_{t_0,t_1\dots,t_9}\left(\dfrac{(\sum t_i)!}{\prod(t_i!)}\cdot\prod\limits_{k\in S}\dfrac{\prod(s_{k,j}^{\underline{t_i}})}{(\sum s_{k,j})^{\underline{(\sum t_i)}}}\right)\right) \end{aligned} \]

于是我们先考虑后半部分式子的贡献，注意到 \(\prod(t_i)!\) 与 \(\prod(s_{k,j}^{\underline{t_i}})\) 都只与 \(t_i\) 有关，于是我们可以单独拿出来做背包，具体地，从 \(t_0\) 到 \(t_9\) 依次进行背包 DP，加入 \(t_i =y\) 时对答案的贡献是其红色部分的乘积，也 就是 \(\dfrac{\prod\limits_{j\in S}s^{\underline y}_{s_{j,i}}}{y!}\)，其中 \(s_{j,i}\) 是 \(S_j\) 中 \(i\) 的出现次数。最后再考虑补充上 \(\sum t_i\) 的贡献。考虑上枚举 \(S\)，时间复杂度为 \(O(2^nm^2)\).

#Code

#define ll long long

const int N = 110;
const int INF = 0x3fffffff;
const int MOD = 998244353;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

char s[N];
int n, m; ll ans, vec[N], dm[N][N], cnt[N][10], w[N], f[N];

inline ll fpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) (res *= x) %= MOD;
        y >>= 1, (x *= x) %= MOD;
    }
    return res;
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; ++ j)
          ++ cnt[i][s[j] - '0'];
    }
    for (int i = 0; i <= m; ++ i) {
        dm[i][0] = 1;
        for (int j = 1; j <= i; ++ j)
          dm[i][j] = dm[i][j - 1] * (i - j + 1) % MOD;
    }
    for (int i = 1; i < (1 << n); ++ i) {
        int tot = 0; ll sum = 0;
        for (int j = 0; j < n; ++ j) 
          if (i & (1 << j)) vec[++ tot] = j + 1;
        f[0] = 1; for (int j = 1; j <= m; ++ j) f[j] = 0;
        for (int j = 0; j <= 9; ++ j) {
            for (int l = 0; l <= m; ++ l) {
                 w[l] = fpow(dm[l][l], MOD - 2);
                 for (int k = 1; k <= tot; ++ k)
                    w[l] = w[l] * dm[cnt[vec[k]][j]][l] % MOD;
            }
            for (int l = m; l >= 0; -- l)
              for (int k = l - 1; k >= 0; -- k)
                (f[l] += f[k] * w[l - k] % MOD) %= MOD;
        }
        for (int j = 0; j <= m; ++ j) {
            ll tmp = f[j] * dm[j][j] % MOD;
            ll prod = fpow(dm[m][j], MOD - 2);
            (sum += tmp * fpow(prod, tot) % MOD) %= MOD;
        }
        if (tot & 1) (ans += sum) %= MOD;
        else ans = (ans - sum + MOD) % MOD;
    }
    printf("%lld", ans); return 0;
}