Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述
维护一个初始为空的多重集。每次从中取出一个元素时，集合中每个元素被取出的概率均等，取出后该元素从集合中删除。每次取出事件相互独立。
给定 nn 次操作序列，操作分为两种：

  1. 向集合中插入一个给定的非负整数。

  2. 从集合中随机取出一个元素。
    保证每次取出时集合非空，且整个操作序列至少包含一次取出操作。
    求所有被取出的元素排成的序列满足单调不降（即序列中每一项都小于等于它的后一项）的概率。答案对 998244353 取模。

输入格式
第一行包含一个正整数 TT（1≤T≤2.5×1031 \le T \le 2.5 \times 10^3），表示测试数据组数。
每组数据第一行包含一个整数 nn（2≤n≤5×1032 \le n \le 5 \times 10^3），表示操作总数。
第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n（−1≤ai≤n-1 \le a_i \le n），表示操作序列：

  • ai≥0a_i \ge 0 表示向集合中插入 aia_i。

  • ai=−1a_i = -1 表示从集合中随机取出一个元素。
    保证所有数据的 ∑n≤5×103\sum n \le 5 \times 10^3。

输出格式
对于每组数据，输出一行一个整数，表示概率对 998244353 取模的结果。

样例输入 1

1
2
3
4
5
6
7
3
3
1 2 -1
5
1 2 -1 3 -1
7
1 2 3 4 -1 -1 -1

样例输出 1

1
2
3
1
249561089
166374059

样例输入 2

1
2
3
4
5
6
7
3
4
1 2 -1 -1
6
1 2 -1 -1 1 -1
8
1 -1 2 -1 3 -1 4 -1

样例输出 2

1
2
3
499122177
0
1

样例解释
对于样例一的第 1 组数据，由于总共只取出了一个元素，序列无论如何都是单调不降的，概率为 1。

对于样例一的第 2 组数据，操作过程和对应概率如下：

  • 加入 1，集合变为 {1}\{1\}；加入 2，集合变为 {1,2}\{1, 2\}。

  • 此时取出 1 的概率为 12\frac{1}{2}。若取出 1，接下来加入 3，集合变为 {2,3}\{2, 3\}。之后无论取出哪个数，得到的序列（1 然后是 2 或 1 然后是 3）均满足单调不降。此情况的合法概率为 12×1=12\frac{1}{2} \times 1 = \frac{1}{2}。

  • 此时取出 2 的概率为 12\frac{1}{2}。若取出 2，接下来加入 3，集合变为 {1,3}\{1, 3\}。之后为了保持单调不降，必须取出 3，取出 3 的概率为 12\frac{1}{2}。此情况的合法概率为 12×12=14\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}。
    最终单调不降的总概率为 12+14=34\frac{1}{2} + \frac{1}{4} = \frac{3}{4}。34\frac{3}{4} 对 998244353 取模的结果为 249561089。

思路讲解

image

这道题目其实不难，就是细节比较多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
for (ll op = 1; op <= cnt_op; ++op) {
    vector<ll> vals;
    for (int val = 0; val <= N; ++val) {
        if (op_val_cnt[op][val] >= 1) {
            vals.push_back(val);
        }
    }
    if (op == 1) {
        for (auto val: vals) {
            dp_val_cnt[val].resize(2);
            // 注意，有多个数字可选的时候，有多种可能，答案不是 1
            dp_val_cnt[val][1] = op_val_cnt[op][val];
            dpacc_val[val] = op_val_cnt[op][val];
        }
    } else {
        vector<vector<ll> > ndp_val_cnt(N + 2);
        vector<ll> ndpacc_val(N + 2);
        vector<ll> presum_dpacc(N + 2);
        // 注意使用前缀和优化
        partial_sum(all(dpacc_val), presum_dpacc.begin(), [](ll a, ll b) {
            return (a + b) % mod;
        });
        for (auto val: vals) {
            ll val_cnt = op_val_cnt[op][val];
            ndp_val_cnt[val].resize(min(op, val_cnt) + 2);
            for (int cnt = 1; cnt <= min(op, val_cnt); ++cnt) {
                ll rem_val = val_cnt - cnt + 1;
                if (cnt >= 2) {
                    if (cnt - 1 > SZ(dp_val_cnt[val]) - 1) {
                        break;
                    }
                    ndp_val_cnt[val][cnt] = rem_val * dp_val_cnt[val][cnt - 1];
                    ndp_val_cnt[val][cnt] %= mod;
                } else {
                    // for (int s_val = 0; s_val < val; ++s_val) {
                    //     ndp_val_cnt[val][cnt] += dpacc_val[s_val];
                    //     ndp_val_cnt[val][cnt] %= mod;
                    // }
                    if (val - 1 >= 0) {
                        ndp_val_cnt[val][cnt] = presum_dpacc[val - 1];
                    }
                    ndp_val_cnt[val][cnt] *= rem_val;
                    ndp_val_cnt[val][cnt] %= mod;
                }
                ndpacc_val[val] += ndp_val_cnt[val][cnt];
                ndpacc_val[val] %= mod;
            }
        }
        swap(dp_val_cnt, ndp_val_cnt);
        swap(dpacc_val, ndpacc_val);
    }
}

AC代码

AC
https://codeforces.com/gym/105941/submission/367931586

心路历程（WA，TLE，MLE……）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
do {
  // 注意，还是要把 numc 显式地写出来
    ll opc = 0, numc = 0;
    vector<ll> cnt(N + 2);
    for (int i = 1; i <= N; ++i) {
        if (A[i] == -1) {
            tot_num *= (numc - opc);
            tot_num %= mod;
            opc++;
            op_val_cnt[opc] = cnt;
        } else {
            cnt[A[i]]++;
            numc++;
        }
    }
} while (false);

Posted on Edited on

2025 National Invitational of CCPC (Zhengzhou), 2025 CCPC Henan Provincial Collegiate Programming Contest

题目大意

给定一个长度为 nn 的数组 aa，初始时第 ii 个位置的值为 aia_i（1≤ai≤n1 \le a_i \le n）。共有 mm 次操作，每次操作给定 l,r,dl, r, d，将区间 [l,r][l, r] 内的值依次替换为 d,d+1,…,d+r−ld, d+1, \ldots, d+r-l。

在初始状态以及每次操作后，输出数组中出现次数最多的值及其出现次数。若有多个值出现次数相同，输出其中编号最小的。

多组测试数据，TT 组，保证 ∑n≤2×105\sum n \le 2 \times 10^5，∑m≤2×105\sum m \le 2 \times 10^5。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
输入：
3
3 3
1 2 3
1 1 2
2 2 3
3 3 1
1 1
1
1 1 1
8 8
7 6 6 4 3 8 5 3
4 4 4
6 8 6
1 1 7
4 7 4
6 7 6
2 7 5
1 5 7
1 6 8

输出：
1 1
2 2
3 2
1 1
1 1
1 1
3 2
3 2
6 3
6 3
6 3
6 3
7 2
8 2
8 2

样例解释（第一组数据）

初始数组为 [1,2,3][1, 2, 3]，三个值各出现 11 次，输出最小编号 11，次数 11。

第 11 次操作 l=1,r=1,d=2l=1, r=1, d=2：将位置 11 替换为 22，数组变为 [2,2,3][2, 2, 3]，值 22 出现 22 次最多，输出 2 22\ 2。

第 22 次操作 l=2,r=2,d=3l=2, r=2, d=3：将位置 22 替换为 33，数组变为 [2,3,3][2, 3, 3]，值 33 出现 22 次最多，输出 3 23\ 2。

第 33 次操作 l=3,r=3,d=1l=3, r=3, d=1：将位置 33 替换为 11，数组变为 [2,3,1][2, 3, 1]，三个值各出现 11 次，输出最小编号 11，次数 11。

思路讲解

我看了一下，宝可梦这道题目珂朵莉树不会被卡的原因是因为全局查询，可以通过维护全局信息解决这个问题。
好像只要改成区间查询，区间修改，珂朵莉树一定会被卡。

珂朵莉树的时间复杂度过于玄学了，我还是想用这个时间复杂度更加确定的算法解决问题。

还是学一下珂朵莉树吧，好像这道题目只能用珂朵莉树，或者至少用珂朵莉树最简单，其他各种各样，形形色色的数据结构，都不是说特别好。

image

不难发现，珂朵莉树只有 assign 操作，肯定是 O(nlog⁡n)O(n\log n)，当然，这个东西没有那么显然，但是不难理解。因为 l，r 越大，需要遍历的区间就越多，但是一次性也把很多区间给整合在一起了。区间小嘛，一共就不遍历几个区间，何谈什么复杂度？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class F>
void assign(ll l, ll r, ll val, F on_change) {
    // 这个顺序对于我们 mp 珂朵莉树实现无所谓
    split(r + 1);
    split(l);
    auto it = mp.lower_bound(l);
    while (it != mp.end() && it->first <= r) {
        ll st=it->first;
        auto [ed,val]=it->second;
        // 具体怎么调用看你的 on_change() 实现，一般是一个全局操作
        on_change();
        it = mp.erase(it);
    }
    mp[l]={r,val};
    on_change();
}

我感觉那种只问一次，或者像这种全局询问的，都非常适合珂朵莉树。

AC代码

AC
https://codeforces.com/gym/105941/submission/368114371

starsilk 的代码

https://codeforces.com/gym/105941/submission/322881549

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目描述

定义函数 f(t)f(t) 为：将字符串 tt 划分为若干部分的最大数量，满足每个部分都是 tt 的非空前缀。

There exist kk strings p1,p2,…,pkp_1,p_2,\ldots,p_k, which are prefixes of tt, such that t=p1+p2+…+pkt=p_1+p_2+\ldots+p_k. Here ++ denotes the string concatenation.

换句话说，f(t)f(t) 是满足以下条件的最大正整数 kk：存在 kk 个字符串 p1,p2,…,pkp_1, p_2, \dots, p_k，它们都是 tt 的前缀，且 t=p1+p2+⋯+pkt = p_1 + p_2 + \dots + p_k（++ 表示字符串拼接）。

给定一个长度为 nn 的小写英文字符串 ss。
你需要回答 qq 次询问，每次询问给出两个整数 lil_i 和 rir_i，要求计算并输出：
∑j=lirif(s[li…j])\sum_{j=l_i}^{r_i} f(s[l_i \dots j])
（其中 s[li…j]s[l_i \dots j] 表示 ss 从第 lil_i 个字符到第 jj 个字符组成的子串）。

image

这个其实是方便我们进行计算的。

输入格式

第一行包含一个整数 tt（1≤t≤1031 \le t \le 10^3），表示测试用例的数量。
每个测试用例的第一行包含两个整数 nn 和 qq（1≤n≤1061 \le n \le 10^6, 1≤q≤1001 \le q \le 100），分别表示字符串长度和询问次数。
第二行包含一个长度为 nn 的小写英文字符串 ss。
接下来 qq 行，每行包含两个整数 lil_i 和 rir_i（1≤li≤ri≤n1 \le l_i \le r_i \le n），表示一次询问。

保证所有测试用例中 nn 的总和不超过 10610^6。

输出格式

对于每次询问，输出一个整数表示表达式的求和结果。

样例数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
输入:
6
1 1
a
1 1
5 2
aaaaa
1 5
2 4
6 2
abcdef
1 6
3 5
6 3
abaaba
1 6
1 3
2 6
7 3
abcabca
1 7
2 7
4 7
8 3
aababaac
1 8
2 8
3 7

输出:
1
15
6
6
3
14
4
7
12
9
5
13
14
7

样例解释

在第一个测试用例中，f(a)=1f(\text{a}) = 1。

在第二个测试用例中：
对于第一次询问 1 5：f(a)+f(aa)+f(aaa)+f(aaaa)+f(aaaaa)=1+2+3+4+5=15f(\text{a}) + f(\text{aa}) + f(\text{aaa}) + f(\text{aaaa}) + f(\text{aaaaa}) = 1 + 2 + 3 + 4 + 5 = 15。
对于第二次询问 2 4（对应的子串是 aaa）：f(a)+f(aa)+f(aaa)=1+2+3=6f(\text{a}) + f(\text{aa}) + f(\text{aaa}) = 1 + 2 + 3 = 6。

在第三个测试用例中：
对于第一次询问 1 6：f(a)+f(ab)+f(abc)+f(abcd)+f(abcde)+f(abcdef)=1+1+1+1+1+1=6f(\text{a}) + f(\text{ab}) + f(\text{abc}) + f(\text{abcd}) + f(\text{abcde}) + f(\text{abcdef}) = 1 + 1 + 1 + 1 + 1 + 1 = 6。
对于第二次询问 3 5（对应的子串是 cde）：f(c)+f(cd)+f(cde)=1+1+1=3f(\text{c}) + f(\text{cd}) + f(\text{cde}) = 1 + 1 + 1 = 3。

思路讲解

P3375 【模板】KMP（前缀函数）（完全理解 kmp）

队友的这个思路，确实是非常好啊。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<ll> shortest_prefix(const vector<ll> &pi) {
    vector<ll> sp(SZ(pi));
    for (int i = 1; i < SZ(pi); ++i) {
        if (pi[i] == 0) {
            sp[i] = 0;
        } else if (sp[pi[i] - 1] > 0) {
            sp[i] = sp[pi[i] - 1];
        } else {
            sp[i] = pi[i];
        }
    }
    return sp;
}

这个方法的正确性还是比较容易看出来的，不言自明，只要前缀和后缀相同。其之所以有效，和 kmp 一样。

image

AC代码

AC
https://codeforces.com/contest/2209/submission/367859558

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题面总结

给定多组数据。每组给出三种幽火数量：红色 r、绿色 g、蓝色 b。

你需要构造一个只由 R、G、B 组成的字符串 s，表示按顺序摆放的幽火颜色，要求：

  • R、G、B 的使用次数分别不超过 r、g、b。

  • 对任意相邻位置，颜色不能相同，即 s_i != s_{i+1}。

  • 对任意间隔 2 个位置（下标差 3）的位置，颜色也不能相同，即 s_i != s_{i+3}。

  • 在满足以上条件下，|s| 要尽可能长。

如果有多个最长可行答案，输出任意一个即可。

输入输出要求

  • 输入第一行为测试组数 t。

  • 每组输入一行三个整数 r g b。

  • 对每组输出一行构造出的字符串 s。

数据范围

  • 1 <= t <= 10^4

  • 0 <= r, g, b <= 10^6

  • r + g + b > 0

  • 所有测试组的 r + g + b 总和不超过 10^6

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
5
0 0 1
1 1 1
0 3 0
2 2 2
2 7 3

输出
B
RGB
G
GBRBRG
GRGRGBGBGBG

样例配合说明

  • 第 1 组：只有 1 个蓝色，输出 B，长度为 1 且合法。

  • 第 2 组：三种颜色各 1 个，RGB 使用了全部 3 个且满足限制。

  • 第 3 组：只有绿色 3 个，但相邻不能同色，所以最多只能放 1 个，输出 G。

  • 第 4 组：GBRBRG 长度为 6，刚好把 2,2,2 全部用完，并满足相邻与间隔 2 的限制。

  • 第 5 组：GRGRGBGBGBG 在给定数量下给出一个满足条件的最长构造。

思路讲解

image

不难发现，能够凑的话，肯定是凑出足够的这个 gb，gr，rb 最好。但是怎么样凑出最多的 gb，gr，rb？其实这个就是求解一个线性方程组（如上），我们可以得到 rb 的这个数量。

但你会发现，如果采用数学式方法，去求解这个二元组的数量，然后去做，肯定是能做出来的，但是坑非常多，首先，这个元组是有可能 rb 求出来是一个负数。

这道题目怎么做？如下。

image

当然，你说为什么就强制给他安一个前缀就对了？其实也没什么神秘的，其实到最后，就是一个奇偶性问题，奇偶性问题有的时候一个的改变，就足以改变正确性了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// 强制枚举前缀
  for (int i = 0; i < pow3[3]; ++i) {
      ll opi = i;
      vector<Num_color> rgb = rgb_global;
      string ans;
      auto push_to_ans = [&](ll i) {
          ans.push_back(rgb[i].color);
          rgb[i].num--;
      };
      auto check_ans = [&]() {
          for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
              if (i - 1 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 1]) {
                  return false;
              }
          }
          for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
              if (i - 3 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 3]) {
                  return false;
              }
          }
          return true;
      };
      auto check_ans_all = [&]() {
          for (int i = SZ(ans) - 1; i >= 0; --i) {
              if (i - 1 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 1]) {
                  return false;
              }
          }
          for (int i = SZ(ans) - 1; i >= 0; --i) {
              if (i - 3 < 0) {
                  break;
              }
              if (ans[i] == ans[i - 3]) {
                  return false;
              }
          }
          return true;
      };
      while (opi != 0) {
          push_to_ans(opi % 3);
          opi/=3;
      }
      if (!check_ans_all()) {
          continue;
      }
      sort(all(rgb), cmp);
      if (rgb[2].num < 0) {
          continue;
      }
      while (true) {
          sort(all(rgb), cmp);
          if (rgb[2].num > 0) {
              push_to_ans(0);
              push_to_ans(2);
              if (!check_ans()) {
                  swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
                  if (!check_ans()) {
                      break;
                  }
              }
              // 以后尽量不要这么写 continue，万一漏了很难 debug 出来
              continue;
          }
          if (rgb[1].num > 0) {
              push_to_ans(0);
              push_to_ans(1);
              if (!check_ans()) {
                  swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
                  if (!check_ans()) {
                      break;
                  }
              }
              continue;
          }
          if (rgb[0].num > 0) {
              push_to_ans(0);
              if (!check_ans()) {
                  ans.pop_back();
                  break;
              }
          }
          break;
      }
      // #ifdef LOCAL
      //         debug(ans);
      //         debug(ans_global);
      // #endif
      if (SZ(ans) > SZ(ans_global)) {
          swap(ans, ans_global);
      }
  }
  cout << ans_global << "\n";

AC代码

AC
https://codeforces.com/contest/2209/submission/367802322

心路历程（WA，TLE，MLE……）

写对拍器的时候，为了防止对拍写的有问题，最好写为不等于，这样子，对拍器生成的字符串过小也可以非常容易的看出来。

1
2
3
4
5
dfs(dfs, "");
if (SZ(brute) != SZ(ans)) {
    cout << "too small\n";
    cout << brute << "\n";
}

Posted on Edited on

题目大意

题目描述
给定两个长度均为 nn 的小写字母字符串 SS 和 TT。
你需要在 SS 中选取一个子串 S′S'，在 TT 中选取一个子串 T′T'（空串不算作子串），并将 T′T' 拼接在 S′S' 的后面组成一个新的字符串。
求共有多少种选取方式，使得拼接后的新字符串是一个回文串。
注：选取方式由子串在原串中的起始和终止位置决定；回文串指正读和反读都相同的字符串。

输入格式
第一行输入一个整数表示测试组数 TT（T≤10T \le 10）。
接下来每组数据输入两行，分别表示字符串 SS 和 TT。
数据保证两个字符串长度相等且 n≤2000n \le 2000。

输出格式
对于每组数据，输出一行整数，表示能组成回文串的子串选取方案数。

样例

样例输入

1
2
3
4
5
2
ab
ac
aba
bba

样例输出

1
2
2
15

样例解释
对于第一组样例，S="ab"S = \text{"ab"}，T="ac"T = \text{"ac"}。合法的选取方式共 22 种：

  1. 选取 S[1…1]="a"S[1 \dots 1] = \text{"a"} 和 T[1…1]="a"T[1 \dots 1] = \text{"a"}，拼接得到 "aa"\text{"aa"}，是回文串。

  2. 选取 S[1…2]="ab"S[1 \dots 2] = \text{"ab"} 和 T[1…1]="a"T[1 \dots 1] = \text{"a"}，拼接得到 "aba"\text{"aba"}，是回文串。

对于第二组样例，S="aba"S = \text{"aba"}，T="bba"T = \text{"bba"}。合法的选取方式共 1515 种，列举其中几种情况：

  • 选取 S[1…1]="a"S[1 \dots 1] = \text{"a"} 和 T[3…3]="a"T[3 \dots 3] = \text{"a"}，拼接得到 "aa"\text{"aa"}。

  • 选取 S[2…2]="b"S[2 \dots 2] = \text{"b"} 和 T[1…1]="b"T[1 \dots 1] = \text{"b"}，拼接得到 "bb"\text{"bb"}。

  • 选取 S[2…2]="b"S[2 \dots 2] = \text{"b"} 和 T[2…2]="b"T[2 \dots 2] = \text{"b"}，拼接得到 "bb"\text{"bb"}。

  • 选取 S[1…2]="ab"S[1 \dots 2] = \text{"ab"} 和 T[2…3]="ba"T[2 \dots 3] = \text{"ba"}，拼接得到 "abba"\text{"abba"}。

  • 选取 S[1…3]="aba"S[1 \dots 3] = \text{"aba"} 和 T[2…3]="ba"T[2 \dots 3] = \text{"ba"}，拼接得到 "ababa"\text{"ababa"}。
    以此类推，满足条件的下标区间组合总共有 1515 种。

思路讲解

完全理解 manacher

image

image

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void Solve() {
    string s;
    string t;
    cin >> s >> t;
    string rev_t = t;
    reverse(all(rev_t));
    ll szs = SZ(s), szt = SZ(t);
    vector<ll> ps = manacher(s);
    vector<ll> pt = manacher(rev_t);
    // 以 i 为起点的这个回文串数量
    vector<ll> cntS(szs + 3), cntT(szt + 3);
    for (int i = 0; i < SZ(ps); ++i) {
        ll r = ps[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntS[pos - r + 1]++;
        cntS[pos + 1]--;
    }
    for (int i = 0; i < SZ(pt); ++i) {
        ll r = pt[i] / 2;
        if (r == 0) {
            continue;
        }
        ll pos = i / 2;
        cntT[pos - r + 1]++;
        cntT[pos + 1]--;
    }
    // 上面是在
    partial_sum(all(cntS), cntS.begin());
    partial_sum(all(cntT), cntT.begin());
#ifdef LOCAL
    debug1d(cntS);
    debug1d(cntT);
#endif
		// 最长公共子后缀
    vector<vector<ll> > lcsuf(szs, vector<ll>(szt));
    ll ans = 0;
    for (int i = 0; i < szs; ++i) {
        for (int j = 0; j < szt; ++j) {
            ll lans = 0;
            if (i - 1 >= 0 && j - 1 >= 0) {
                lans = lcsuf[i - 1][j - 1];
            }
            lcsuf[i][j] = lans;
            if (s[i] == rev_t[j]) {
                lcsuf[i][j]++;
            } else {
                lcsuf[i][j] = 0;
            }
            // 加一是因为还有空的情况，即 s 和 rev_t 都不提供 B
            ll add = lcsuf[i][j] * (cntS[i + 1] + cntT[j + 1] + 1);
            ans += add;
        }
    }
    cout << ans << "\n";
}

AC代码

TLE，这个代码是这个 O(n2)O(n^2) 的，但是还是这个哈希表还是有点慢，被卡了。

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1197&rid=19239

心路历程（WA，TLE，MLE……）