2024 ccpc 网络赛题解

比赛链接：https://codeforces.com/gym/105336

L. 网络预选赛

题意

给出一个 $n\ast m$ 的字符矩阵，问该矩阵内存在多少个子矩阵 $[\begin{array}{c}cc\\ pc\end{array}]$。

数据范围

$2\le n,m\le 500$

思路

两重循环遍历字符矩阵，找到所有为 $[\begin{array}{c}cc\\ pc\end{array}]$ 的子矩阵即可

复杂度

时间复杂度 $O(n\ast m)$，空间复杂度 $O(n\ast m)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 505;

int n, m;
string g[N];

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }
    int ans = 0;
    for (int i = 0; i + 1 < n; i++) {
        for (int j = 0; j + 1 < m; j++) {
            if (g[i][j] == 'c' && g[i][j + 1] == 'c'
                && g[i + 1][j] == 'p' && g[i + 1][j + 1] == 'c')
                ans++;
        }
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

延伸思考

如果是对于一个 $n\ast m$ 的字符矩阵 $S$，要查询一个 $a\ast b$ 的字符矩阵 $T$ 在 $S$ 中出现的次数？（$1\le a\le n,1\le b\le m$）
例题链接：https://vjudge.net/problem/UVA-11019

字符串哈希

思路

可以对二维的字符矩阵处理哈希值，和一维的字符串哈希类似，不同的是处理二维的时候，是先处理其中一维度的哈希值，然后把该维的值作为另一维哈希值中某一位上的数。

处理 $T$ 的哈希值，先对 $T$ 的每一行，以 $bas{e}_1$为底数进行字符串哈希的处理，得到 $v_1,v_2,...,v_a$，然后再取 $bas{e}_2$为底数，$v_1\ast bas{e}_2^{a-1}+v_2\ast bas{e}_2^{a-2}+...+v_n$即为 $T$的哈希值，这步的时间复杂度为 $O(a\ast b)$。
然后处理出 $S$每一行的前缀字符串哈希值，用于求某行中子串的哈希值。

若 $S$中的 $a\ast b$的子矩阵的右下角 $(i,j)$（表示第 $i$行第 $j$列，下同），令 $hash(i,l,r)$为$S$中第$i$行中区间为$[l,r]$的子串的哈希值，则该子矩阵的哈希值为 $hash(i-a+1,j-b+1,j)\ast bas{e}_2^{a-1}+...+hash(i,j-b+1,j)$。

枚举子矩阵的右下角 $(i,j)$，看是否存在子矩阵哈希值和 $T$的哈希值相同，枚举顺序是先列后行，因为按上面这个哈希规则，从右下角为 $(i,j)$的子矩阵转移到右下角为 $(i+1,j)$的子矩阵，子矩阵的哈希值变化很少，就是减去了 $hash(i-a+1,j-b+1,j)\ast bas{e}_2^{a-1}$这一项，然后剩下的部分乘上 $bas{e}_2$，再增加 $hash(i+1,j-b+1,j)$，就变成右下角为 $(i+1,j)$的子矩阵的哈希值，而如果先行后列，哈希值中涉及到 $a$行，每一行的值就要改动，因此先列后行枚举是较优的，最多枚举 $(n-a+1)\ast (m-b+1)$个右下角就可以枚举完所有的子矩阵，复杂度是 $O(n\ast m)$的。

复杂度

时间复杂度为 $O(n\ast m+a\ast b)$，空间复杂度为 $O(n\ast m)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef unsigned long long ull;

const int N = 1e3 + 1, M = 1e2 + 5;
const ull base1 = 13331, base2 = 1e9 + 7;

int n, m, a, b, q;
ull p, p1, s[N][N];
string g[N], g1[M];

ull gethash(int l, int r, ull h[])
{
    return h[r] - h[l - 1] * p;
}

void solve()
{
    cin >> n >> m;
    // 读入n*m的字符矩阵
    for (int i = 1; i <= n; i++) {
        cin >> g[i];
        g[i] = ' ' + g[i];
    }
    cin >> a >> b;
    ull val = 0;
    // 读入a*b的字符矩阵,同时处理出该矩阵的哈希值val
    for (int i = 1; i <= a; i++) {
        cin >> g1[i];
        ull cur = 0;
        for (char c : g1[i]) {
            cur = cur * base1 + c;
        }
        val = val * base2 + cur;
    }
    if (a > n || b > m) {
        cout << 0 << '\n';
        return;
    }

    // 处理n*m的字符矩阵每一行的哈希值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] = s[i][j - 1] * base1 + g[i][j];
        }
    }

    // p = base1的b次方,在求n*m矩阵中某一行长度为b的子串的哈希值中用到
    p = 1;
    for (int i = 1; i <= b; i++) {
        p *= base1;
    }
    // p1 = base2的a-1次方,在计算n*m矩阵中a*b的子矩阵的哈希值用到
    p1 = 1;
    for (int i = 1; i < a; i++) {
        p1 *= base2;
    }
	// cnt 为出现次数
    int cnt = 0;
    // 双重循环 (i,j) 枚举的是a*b的子矩阵的右下角
    for (int j = b; j <= m; j++) {
        ull cur = 0;
        // cur 为当前枚举的a*b的子矩阵的哈希值
        for (int i = 1; i <= n; i++) {
            cur = cur * base2 + gethash(j - b + 1, j, s[i]);
            if (i >= a) {
                // 找到一个子矩阵哈希值和 T的哈希值val 相同
                if (val == cur)
                    cnt++;
                cur -= p1 * gethash(j - b + 1, j, s[i - a + 1]);
            }
        }
    }
    cout << cnt << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

kmp

思路

如果要看 $S$中以 $(i,j)$为左上角，大小为 $a\ast b$的子矩阵是否为 $T$，一般的想法都是从第 $i$行开始，看第 $i$行中区间为 $[j,j+b-1]$对应的子串是否和 $T$的第一行相同，如果相同，就看第 $i+1$行中区间为 $[j,j+b-1]$对应的子串是否和 $T$的第二行相同，如果不同，说明以 $(i,j)$为左上角的 $a\ast b$的子矩阵一定不为 $T$，结束匹配，若可以匹配到第 $i+a-1$行，且该行区间为 $[j,j+b-1]$对应的子串和 $T$的第 $a$行相同，那么该子矩阵就为 $T$。

从这个思路出发，可以取 $S$的每一行与 $T$的第一行进行匹配，找出在 $S$每行的哪些位置开始，长度为 $b$的子串为 $T$的第一行，然后保留这些位置。
接着，取 $S$的每一行与 $T$的第二行进行匹配，找出在 $S$每行的哪些位置开始，长度为 $b$的子串为 $T$的第二行，如果$(i,j)$为第二轮找到的位置，且$(i-1,j)$为第一轮找到的位置，说明从$(i,j)$开始向下匹配，至少能与 $T$的前两行匹配，对于 $(i,j)$这样的位置进行保留。
然后进行第三轮，第三轮也是类似的，，如果$(i,j)$为第三轮找到的位置，且$(i-1,j)$为第二轮保留的位置，说明从$(i,j)$开始向下匹配，至少能与 $T$的前三行匹配，对于 $(i,j)$这样的位置进行保留。
如果到第 $k$轮没有可以保留的位置，说明 $S$中不存在能匹配 $T$前 $k$行的子矩阵，也说明 $S$中不存在 $k$，否则如果到第 $a$轮都有可以保留的位置，说明 $S$中存在能匹配 $T$前 $a$行的子矩阵，即 $S$中存在 $T$。
在实际代码实现中，因为每一轮要保留的位置只与前一轮保留的位置相关，所以每进行一轮后，可以把上一轮保留的位置清空，这样就能保证进行每一轮时，当前保留的位置是近似 $n\ast m$的，从而优化空间复杂度。

使用 $kmp$进行字符串匹配，每行匹配的复杂度是 $O(m+b)$，最多进行 $a$轮匹配，每轮最多匹配的行数接近 $n$，所以最坏复杂度是 $O(a\ast n\ast (m+b))$

复杂度

时间复杂度 $O(a\ast n\ast (m+b))$，空间复杂度 $O(n\ast m)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef unsigned long long ull;

const int N = 1e3 + 1, M = 1e2 + 5;

// st[i][j] = 1 表示上一轮保留了(i,j), =0 则反之
int n, m, a, b, ne[M], st[N][N];
string g[N], g1[M];

// 求s的前缀数组ne
void init(string& s)
{
    for (int i = 2, j = 0; i <= b; i++) {
        while (j && s[i] != s[j + 1])
            j = ne[j];
        if (s[i] == s[j + 1])
            j++;
        ne[i] = j;
    }
}

void solve()
{
    cin >> n >> m;
    // 读入n*m的字符矩阵
    for (int i = 1; i <= n; i++) {
        cin >> g[i];
        g[i] = ' ' + g[i];
    }

    cin >> a >> b;
    // 读入a*b的字符矩阵
    for (int i = 1; i <= a; i++) {
        cin >> g1[i];
        g1[i] = ' ' + g1[i];
    }

    if (a > n || b > m) {
        cout << 0 << '\n';
        return;
    }

    for (int i1 = 1; i1 <= a; i1++) {
        // 计算T第i1行的前缀数组
        init(g1[i1]);
        vector<array<int, 3>> pos;
        // 记录该轮找到的位置
        for (int i = 1; i <= n; i++) {
            for (int j = 1, j1 = 0; j <= m; j++) {
                while (j1 && g[i][j] != g1[i1][j1 + 1])
                    j1 = ne[j1];
                if (g[i][j] == g1[i1][j1 + 1])
                    j1++;
                if (j1 == b) {
                    pos.push_back({ i, j, 0 });
                }
            }
        }
        // 如果该轮没有找到位置则不存在子矩阵为T
        if (!pos.size()) {
            cout << 0 << '\n';
            return;
        }
        for (auto& it : pos) {
            int i = it[0], j = it[1];
            if (st[i - 1][j] || i1 == 1) {
                it[2] = 1;
            }
        }
        // 清空上一轮保留的位置
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                st[i][j] = 0;
            }
        }
        // 该轮保留的位置进行标记
        for (auto it : pos) {
            int i = it[0], j = it[1];
            if (it[2])
                st[i][j] = 1;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cnt += st[i][j];
        }
    }
    cout << cnt << '\n';
    // cnt为 T 在 S中的出现次数
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

B. 军训 II

题意

给出一个长度为 $n$ 的序列，定义序列的 “不整齐度” 为 ${\sum }_{l=1}^n{\sum }_{r=l}^{n}max(a_l,a_{l+1},...,a_r)-min(a_l,a_{l+1},...,a_r)$，即为所有区间的极差和。

可以将序列进行重新排列，问重新排列后序列可以取到的 “不整齐度” 最小值和对应的方案数。
（注：这里的重新排列指对数的下标进行重新排列，因此，如果在原序列中 $a_i=a_j$，$(a_i,a_j)$,$(a_j,a_i)$ 是两种不同的排列方案）

（答案对 $998244353$ 取模)

数据范围

$1\le n\le 10^3,1\le a_i\le 10^6$

思路

结论
当序列为升序或者降序的时候，不整齐度为最小值。

证明如下：
当序列长度为 $n$ 的时候，若序列的最大值为 $x$，那么不存在比 $x$ 大的数，$x$ 对不整齐度的贡献只有当 $x$ 为区间最大值的情况，只会产生正贡献。

如果 $x$ 的下标为 $i$，那么会有 $i\ast (n-i+1)$ 个区间包含 $x$，$x$ 对不整齐度的贡献为 $i\ast (n-i+1)\ast x$，因为 $x$ 为常数，所以该贡献的大小取决于 $i\ast (n-i+1)=-i^2+(n+1)\ast i$，可以发现这是一个凸函数，它的极大值点在 $\frac{n+1}{2}$，在两侧取得最小值，所以考虑把最大值先放到最左边或者最右边。

接着序列的长度就变成了 $n-1$，如果当前序列的最大值为 $x_1$，那么如果不考虑 $x$ 的话，$x_1$ 也是选择最左侧或者最右侧放是最优的（注意，如果与 $x$ 放在同一侧，比如都放在最右侧，这里 $x_1$ 是要放在$x$ 的左边一位，反之同理），如果 $x_1$ 与 $x$ 不放在同一侧，如果 $n>2$，那么 $x_1$ 和 $x$ 之间存在不大于 $x_1$ 的数，从而使得 $x_1$ 无法作为区间的最小值，只有作为区间最大值贡献的部分，如果 $x_1$ 和 $x$ 放在同一侧，与 $x$ 相邻，那么 $x_1$ 原先作为作为区间最大值贡献的部分不变，且可以作为区间最小值产生负贡献，因此，把次大值放在与最大值同一侧是最优的。

之后长度减一，可以发现仍然是相同的子问题，把序列的当前最大值，与之前安排的序列最大值放在同一侧，是最优的做法，这样放置之后，序列必然要么降序要么升序。

通过以上结论，可以之间对序列进行升序排序，然后从小到大枚举区间的左，右端点。
如果当前枚举的区间端点为 $i$，那么当 $i$ 为区间右端点时，$a_i$ 会作为区间的最大值，对应的左端点选择区间为 $[1,i]$，有 $i$ 种选择，对 “不整齐度” 的贡献为 $i\ast a_i$，当 $i$ 为左端点时，$a_i$ 会作为区间的最小值，对应的右端点选择区间为 $[i,n]$，有 $n-i+1$ 种选择，对 “不整齐度” 的贡献为 $-(n-i+1)\ast a_i$，把所有的贡献加起来即为可以取到的最小 “不整齐度” 。

当序列升序或者降序时，相等的数必然是连续的一段，对于相等的数，虽然这些数相等，但是它们对应的原下标不同，如果放在不同的位置，则对应不同的情况。在这一段中对这些相等的数进行任意排列，“不整齐度” 仍然是最小的，所以如果序列中 $x$ 的出现次数为 $y$，那么对应的排列情况为 $y!$ 种，利用乘法原理，对序列中，存在的不重复的数的数量的阶乘，进行累乘，得到的乘积 $val$ 即为升序或者降序时的情况数。

如果序列中只存在一种数，那么升序和降序都是一样的，此时答案为 $val$，否则，升序和降序不一样，此时的答案为 $val\ast 2$。

复杂度

时间复杂度为 $O(n\log n)$，主要是排序的复杂度
空间复杂度为 $O(n)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e3 + 5, mod = 998244353;

int n;
set<int> nums;
int a[N], f[N];

void solve()
{
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        nums.insert(a[i]);
        // 通过set去重,set的大小 nums.size() 即为序列中数的种类数量
        f[i] = i * f[i - 1] % mod;
        // 预处理阶乘
    }
    sort(a + 1, a + 1 + n);
    int mi = 0;
    for (int i = 1; i <= n; i++) {
        mi += a[i] * (i - 1) - a[i] * (n - i);
        // 正贡献: a[i] * (i-1)
        // 负贡献: -a[i] * (n-i)
    }
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        int j = i;
        while (j <= n && a[i] == a[j])
            j++;
        // 通过双指针找到相等的数的区间长度 j-i
        cnt = (cnt * f[j - i]) % mod;
        i = j - 1;
    }
    if (nums.size() > 1)
        cnt = cnt * 2 % mod;
    cout << mi << ' ' << cnt;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

K. 取沙子游戏

题意

存在 $n$ 粒沙子，$Alice$ 和 $Bob$ 两人轮流取沙子，$Alice$ 先取，每次取的数量不难超过 $k$，且为前面所有取的沙子数量的公因数，先取完沙子的人获胜。

问两个人都采取最优策略，$Alice$ 是否可以获胜。

数据范围

$1\le T\le 10^4$，表示数据组数，$1\le n,k\le 10^9$

思路

结论

如果 $lowbit(n)\le k$，那么 $Alice$ 必胜，否则 $Bob$ 必胜。（注：如果 $n$ 在二进制下存在 $1$ 的最低位为 $i$，那么 $lowbit(n)=2^i$。）

证明

令 $n=2^{p_1}+2^{p_2}+2^{p_3}+...2^{p_m}(p_1<p_2<p_3<...<p_m)$。

如果 $lowbit(n)\le k$，那么 $Alice$ 可以先取 $lowbit(n)$，取走之后，$n=2^{p_2}+2^{p_3}+..+2^{p_m}$。

因为 $p_1$ 最小为 $0$，所以 $p_2,p_3,...,p_m$ 都大于 $0$，此时 $n$ 必然为偶数，所以在接下来 $Bob$ 每次操作之后， $Alice$ 可以重复 $Bob$ 的取的数，由于偶数可以取半，所以按这样的策略 $n$ 必然能取完，且因为 $Alice$ 是在 $Bob$ 操作之后取，所以取完的时候必然是轮到 $Alice$。

否则，如果 $lowbit(n)>k$，那么 $Alice$ 起初取任意数 $x(x\le k)$，因为 $lowbit(x)\le k<lowbit(n)$，$n$
在 $lowbit(x)$ 对应二进制位上的数为 $0$，减去 $x$ 之后，$n$ 在 $lowbit(x)$ 对应的二进制位上的数必然会变成 $1$，此时 $lowbit(n-x)=lowbit(x)\le k$，$Bob$ 就处于必胜的状态，$Alice$ 必输。

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, k;

void solve()
{
    cin >> n >> k;

    // 因为1e9 < 2的32次方,所以枚举从低到高32位
    for (int i = 0; i <= 32; i++) {
        // 找存在1的最低位
        if ((n >> i) & 1) {
            int w = 1ll << i;
            // w = 2的i次幂 = lowbit(n)
            cout << (w <= k ? "Alice" : "Bob") << '\n';
            return;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D. 编码器-解码器

题意

给出两个字符串 $S,T$。

若 $S$ 的长度为 $n$，则进行 $n$ 轮计算，得到一个字符串 $R_n$。

计算方式如下，

$R_i=\{\begin{array}{l}{S}_i,i=1\\ R_{i-1}+S_i+R_{i-1}，i>1\end{array}$

比如，$S=abc$，则 $R_1=S_1=a,R_2=R_1+S_2+R_1=aba,R_3=R_2+S_3+R_2=abacaba$。

问在 $R_n$ 中，$T$ 以咨询了形式出现的次数？
（答案对 $998244353$ 取模)

数据范围

$1\le |S|,|T|\le 100$

思路

注意到，$R_i=R_{i-1}+S_i+R_{i-1}$，令前面的 $R_{i-1}$ 为 $P_1$，后面的 $R_{i-1}$ 为 $P_2$，则 $R_i=P_1+S_i+P_2$。

如果 $T$ 在 $R_i$ 中以子序列存在，如果不考虑 $S_i$，那么 $T$ 必然是存在一部分 $T_1$ 在 $P_1$ 中，存在一部分 $T_2$ 在 $P_2$ 中（$T_1,T_2$ 满足 $T=T_1+T_2$）；或者都在 $P_1$ 中；或者都在 $P_2$ 中，后面两种情况可以看作 $T_1$ 或者 $T_2$ 为空串的情况。

如果 $T_1$ 在 $P_1$ 中以子序列出现的次数为 $v_1$，$T_2$ 在 $P_2$ 中以子序列出现的次数为 $v_2$，那么在不考虑 $S_i$ 的情况下，通过乘法原理可得，$T$ 在 $R_i$ 中以子序列出现的次数为 $v_1\ast v_2$。

如果考虑 $S_i$，其实是同理的，引用上面的定义，$T_1,T_2$ 分别为 $T$ 在 $P_1,P_2$ 中存在的部分，此时 $T_1,S_i,T_2$ 满足 $T=T_1+S_i+T_2$，那么在考虑 $S_i$ ，且 $S_i$ 可以作为子序列的一部分的情况下，若 $T_1$ 在 $P_1$ 中以子序列出现的次数为 $w_1$，$T_2$ 在 $P_2$ 中以子序列出现的次数为 $w_2$，$T$ 在 $R_i$ 中以子序列出现的次数为 $w_1\ast w_2$。

因为 $T_1,T_2$ 是不确定的，对应着 $T$ 的多个子串，且要计算子串在 $R_i$ 中以子序列出现的次数，也涉及到其他子串，所以要计算 $T$ 所有的子串在 $R_i$ 中以子序列出现的次数，才能通过子串的次数推出 $T$ 的次数。

子串和上面 $T$ 的计算方法是一样的，存在着从 $R_{i-1}$ 推到 $R_i$，从 $T$ 的小子串推到 $T$ 的大子串这样的关系，可以考虑用动态规划解决这个问题。

令 $f(i,j,k)$ 为在 $R_i$ 中，$T$ 中从下标 $j$ 开始，长度为 $k$ 的子串，以子序列形式出现的次数。

若 $|S|=n,|T|=m$，则 $1\le i\le n,1\le j\le m,0\le k\le m-j+1$

在上面的讨论过程中，涉及到空串的情况，因为这是一种合法情况，所以在初始化的时候，设置 $f(i,j,0)=1(1\le i\le n,1\le j\le m+1)$。（$j$ 最大为 $m+1$ 的原因，下面状态转移会解释到）

当 $i=1$ 时，因为 $R_1=S_1$，所以如果 $S_1=T_j$，则 $T_j$ 可以作为 $R_1$ 的子序列，$f(1,j,1)=1$。

当 $i>1$ 时，$f(i,j,k)$ 对应的状态会分为两种情况：

1，不考虑 $S_i$

若从下标 $j$ 开始，长度为 $x$ 的部分在 $P_1$ 中，则剩下的部分，即从下标 $j+x$ 开始，长度为 $k-x$ 的部分在 $P_2$ 中。

因为 $P_1=P_2=R_{i-1}$，因此长度为 $x$ 的部分在 $P_1$ 中以子序列出现的次数为 $f(i-1,j,x)$，从下标 $j+x$ 开始，长度为 $k-x$ 的部分在 $P_2$ 中以子序列出现的次数为 $f(i-1,j+x,k-x)$，该情况对应的子序列出现次数则为 $f(i-1,j,x)\ast f(i-1,j+x,k-x)$。

因为 $x$ 的取值范围为 $[0,k]$，所以不考虑 $S_i$，从下标 $j$ 开始，长度为 $k$ 的子串，在 $R_i$ 中以子序列形式出现的次数为 ${\sum }_{x=0}^{k}f(i-1,j,x)\ast f(i-1,j+x,k-x)$。

注意，在计算类似 $f(i,1,m)$ 涉及到右边界的状态时，会涉及到 $f(i-1,m+1,0)$，这里 $f(i,1,m)$ 会涉及到 $f(i-1,1,m),f(i-1,m+1,0)$，表示 $T$ 从下标 $1$ 开始，长度为 $m$ 的部分都在 $P_1$ 的情况，这是合法的情况，所以要设置 $f(i-1,m+1,0)=1$，否则默认为 $0$ 可能会使得一些状态没有算进去。

2，考虑 $S_i$
从下标 $j$ 开始，长度为 $x-1$ 的部分在 $P_1$ 中，然后 $T_{j+x-1}$ 为 $S_i$，从下标 $j+x$ 开始，长度为 $k-x$ 的部分在 $P_2$ 中。

和不考虑 $S_i$ 的情况是同理的，就是需要判断 $T_{j+x-1}$ 是否和 $S_i$ 相同，如果不同的话，那么对应情况不成立，否则对应情况的以子序列出现的次数为 $f(i-1,j,x-1)\ast f(i-1,j+x,k-x)$。

因为 $x-1$ 最小为 $0$，所以 $x$ 的取值范围为 $[x,k]$，因此考虑 $S_i$，，从下标 $j$ 开始，长度为 $k$ 的子串，在 $R_i$ 中以子序列形式出现的次数为 ${\sum }_{x=1}^{k}f(i-1,j,x-1)\ast f(i-1,j+x,k-x)\ast [S_i==T_{j+x-1}]$。（ $[]$ 表示艾佛森括号，若 $x$ 成立则 $[x]=1$，否则 $[x]=0$）

综上，当 $i>1$ 时，$f(i,j,k)={\sum }_{x=0}^{k}f(i-1,j,x)\ast f(i-1,j+x,k-x)+{\sum }_{x=1}^{k}f(i-1,j,x-1)\ast f(i-1,j+x,k-x)\ast [S_i==T_{j+x-1}]$

复杂度

时间复杂度 $O(|S||T{|}^3)$，遍历所有的状态复杂度为 $O(|S||T{|}^2)$，状态计算的复杂度为 $O(|T|)$
空间复杂度 $O(|S||T{|}^3)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e2 + 5, mod = 998244353;

int n, m;
string s, t;
int f[N][N][N];

void solve()
{
    cin >> s >> t;
    n = s.size(), m = t.size();
    s = ' ' + s, t = ' ' + t;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m + 1; j++) {
            f[i][j][0] = 1;
        }
    }
    for (int i = 1; i <= m; i++) {
        f[1][i][1] = s[1] == t[i];
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 1; j + k - 1 <= m; k++) {
                for (int x = 0; x <= k; x++) {
                    f[i][j][k] = (f[i][j][k] + f[i - 1][j][x] * f[i - 1][j + x][k - x] % mod) % mod;
                    if (x > 0 && s[i] == t[j + x - 1]) {
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][x - 1] * f[i - 1][j + x][k - x] % mod) % mod;
                    }
                }
            }
        }
    }
    cout << f[n][1][m];
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

E. 随机过程

题意

有 $n$ 个长度为 $m$ 的字符串，每个字符串的每一位字符都是 $[a,z]$ 中等概率随机选一个。
将 $n$ 个字符串插入字典树，问字典树上节点个数的最大值与期望。

（答案对 $998244353$ 取模）

数据范围

$1\le n,m\le 10^5$

思路

如果到达字典树的某个节点，要插入字符串的某个字符时，如果该节点存在对应字符的子节点，就会走向子节点，然后插入下一个字符，否则就会新建子节点后再操作。

因为字符集为 $[a,z]$，所以一个节点最多会存在 $26$ 个子节点，第 $i$ 层的最大节点数为 $26^i$。

如果 $26^i\ge n$，则插入 $n$ 个字符串，总能新建$n$ 个不同节点插入 $n$ 个字符串的第 $m$ 位字符，否则最多新建 $26^i$ 个节点。

由于字符串的长度为 $m$，算上根节点的一层，字典树的层数为 $m+1$，因此字典树中节点个数的最大值为 ${\sum }_{i=0}^{m}min(26^i,n)$。

对于字典树第 $i$ 层的一个节点，令从根节点到该节点的边所构成的字符串为 $T$，若只插入一个字符串，该节点要存在的话，$T$ 必然为插入的字符串的前缀，因为 $T$ 的长度为 $i$，所以该节点存在的概率为 $\frac{1}{26^i}$，不存在的概率为 $1-\frac{1}{26^i}$。

但是此时的问题是插入 $n$ 个字符串，如果该节点存在，那么可能是有一个字符串的前缀为 $T$，有两个字符串的前缀为 $T$，…，有 $n$ 个字符串的前缀为 $T$，情况很多不好求，但是可以不存在的概率是好求的，该节点不存在意味着 $n$ 个字符串都不存在前缀 $T$，只有一种情况，对应概率为 $(1-\frac{1}{26^i}{)}^n$，因此字典树第 $i$ 层的某个节点存在的概率为 $1-(1-\frac{1}{26^i}{)}^n$。

因为第 $i$ 层的最多存在的节点数为 $26^i$，而每个节点都是等概率的，所以第 $i$ 层的期望节点数为 $26^i\ast (1-(1-\frac{1}{26^i}{)}^n)$，字典树有 $m$ 层，则字典树的期望节点数为 ${\sum }_{i=0}^{m}26^i\ast (1-(1-\frac{1}{26^i}{)}^n)$。

因为答案对 $998244353$ 取模，所以 $\frac{1}{26^i}$ 需要转换为在 $998244353$ 模意义下的乘法逆元，可以利用费马小定理和快速幂求解，求每层的节点数也可以用快速幂求解。

复杂度

时间复杂度为 $O(m\log n)$，$O(m)$ 为遍历层数的复杂度，$O(\log n)$ 是计算每一层期望节点数使用的快速幂的复杂度。
空间复杂度为 $O(1)$

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 998244353;

int n, m;

int qmi(int a, int b)
{
    a %= mod;
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

int inv(int x)
{
    return qmi(x, mod - 2);
}

void solve()
{
    cin >> n >> m;
    int ma = 1, cur = 1;
    for (int i = 1; i <= m; i++) {
        cur = min(cur * 26, n);
        ma = (ma + cur) % mod;
    }
    cout << ma << ' ';

    int sum = 0;
    for (int i = 0; i <= m; i++) {
        int p = qmi(1 - qmi(inv(26), i) + mod, n);
        // 不存在的概率
        int q = (1 - p + mod) % mod;
        // 存在的概率
        int num = qmi(26, i);
        // 该层节点数
        sum = (sum + num * q % mod) % mod;
    }
    cout << sum;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

J. 找最小

题意

给出两个长度为 $n$ 的序列 $a,b$，可以若干次选择一个下标 $i$，然后交换 $a_i,b_i$。

令 $f(A)={\oplus }_{i=1}^n{A}_i$，问若干次交换之后，$max(f(a),f(b))$ 最小可能是多少？

数据范围

$1\le T\le 10^5$，$T$ 表示数据组数
$1\le n,\sum n\le 10^6,0\le a_i<2^{31}$

思路

设最开始未进行交换时候的 $f(a)=xa,f(b)=xb$。

如果交换 $a_i,b_i$，通过异或的性质 $x\oplus x=0$，那么交换之后 $f(a)=xa\oplus a_i\oplus b_i=(a_1\oplus a_2\oplus ...\oplus a_n)\oplus a_i\oplus b_i=a_1\oplus a_2\oplus ...\oplus b_i\oplus ...\oplus a_n,f(b)=xb\oplus a_i\oplus b_i$。

设 $c_i=a_i\oplus b_i$，那么选择若干个下标进行交换，就相当于选择 $c$ 中的子序列，若选择的子序列异或和为 $v$，那么交换后 $f(a)=xa\oplus v,f(b)=xb\oplus v$，此时问题就转换为找出一个 $c$ 的子序列异或和 $v$，能使得 $max(xa\oplus v,xb\oplus v)$ 最小化。

子序列异或问题可以用异或线性基解决，异或线性基就是通过序列构造的一个集合，该集合任意一个子集的异或和都对应序列中某个子序列的异或和。

异或线性基中，每个元素都有不同的二进制的最高有效位，即每个元素在二进制下最高位的 $1$ 所在的位数是不同的。

因为越高位权重越大，所以应该优先消去 $xa,xb$ 高位上的 $1$，因此可以按最高有效位，从高到低地遍历通过 $c$ 构造出的线性基中的元素，如果 $xa,xb$ 与当前遍历到的元素进行异或后，使得 $max(xa,xb)$ 变小，那么就异或上该元素，这样遍历一次之后，得到的 $max(xa,xb)$ 即为可以取到的最小值。

复杂度

时间复杂度为 $O(n{\log }_2{a}_i)$，因为涉及遍历二进制位，所以通过序列构造线性基的复杂度为 $O(n{\log }_2{a}_i)$。
空间复杂度为 $O(max({\log }_2{c}_i))$，因为线性基中的元素最高有效位不同，所以线性基中元素数量最多为 $c_i$ 的最大二进制位数。

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5, M = 32;

int n;
int a[N], b[N], p[M];

// 向线性基中插入x
void insert(int x)
{
    for (int i = M - 1; i >= 0; i--) {
        if ((x >> i) & 1) {
            if (!p[i]) {
                p[i] = x;
                break;
            }
            x ^= p[i];
        }
    }
}

void solve()
{
    cin >> n;
    int sa = 0, sb = 0;
    // sa,sb为序列a,b的初始异或和
    memset(p, 0, sizeof(p));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sa ^= a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        sb ^= b[i];
        insert(a[i] ^ b[i]);
    }
    for (int i = M - 1; i >= 0; i--) {
        int xa = sa ^ p[i];
        int xb = sb ^ p[i];
        if (max(xa, xb) < max(sa, sb)) {
            sa = xa, sb = xb;
        }
    }
    cout << max(sa, sb) << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}