2022杭电多校（一）

2022杭电多校（一）

一、比赛小结

比赛链接：2022杭电多校 (hdu.edu.cn)

二、题目分析及解法（基础题） 1001、String

题目链接：Problem - 7138 (hdu.edu.cn)

题意：

有一串长度 n   ( n ≤ 1 0 6 ) n \ (n\le 10^6) n (n≤106) 的字符串，我们定义关于 G G G 的函数 F G F_G FG​ 为满足以下条件的正整数 x x x 的数量：

1. 1 ≤ x ≤ G l e n 1\le x\le G_{len} 1≤x≤Glen​

2. G [ 1 ， x ] = G [ G l e n − x + 1 ， G l e n ] G[1，x]=G[G_{len}−x+1，G_{len}] G[1，x]=G[Glen​−x+1，Glen​]

3. 区间 [ 1 ， x ] [1，x] [1，x] 和 [ G l e n − x + 1 ， G l e n ] [G_{len}−x+1，G_{len}] [Glen​−x+1，Glen​] 的 LCS 长度大于 0 并且可被 k 整除

求 ∏ i = 1 n ( F S [ 1 , … , i ] + 1 ) ( m o d 998244353 ) \displaystyle \prod_{i=1}^n(F_{S[1,\dots,i]}+1) \pmod {998244353} i=1∏n​(FS[1,…,i]​+1)(mod998244353)

题解：

其实是一道简单的字符串题目，但比赛时过的人很少，我们考虑 [ 1 , n ] [1,n] [1,n] 和 [ i , n ] [i,n] [i,n] 的最长公共前缀，exkmp 可以快速求出。并设为 [ 1 , x ] [1,x] [1,x] 和 [ i , i + x − 1 ] [i,i+x-1] [i,i+x−1] ，那么考虑其交叉部分，即 [ i , x ] [i,x] [i,x] 。我们发现可以截取出 [ i , i − 1 + t ∗ k ] [i,i-1+t*k] [i,i−1+t∗k] ，那么考虑其贡献，为 a n s [ ] ans[] ans[] 数组进行贡献 +1 ，朴素实现会超时，利用模 k 意义下的差分即可解决。

代码：

#include 
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 1e6 + 5;
int n, k;
int res[maxn];
int exnext[maxn];
char s[maxn];
void getexnext() {
  int i = 0, j, pos;
  exnext[0] = n;
  while (s[i] == s[i + 1] && i + 1 > k;
    n = strlen(s);
    memset(res, 0, sizeof res);
    getexnext();
    for (int i = 0; i = i - 1 + k) {
        int p1 = 2 * i - 1 + k;
        int len = (exnext[i] - i) / k * k;
        if (p1  edge[i].x1 >> edge[i].y1 >> edge[i].x2 >> edge[i].y2;
    for (int state = 0; state = res) continue;
      memset(ans, false, sizeof ans);
      ans[xs][ys] = true;
      if (bfs(state)) res = cnt;
    }
    cout  w[i];
    f[0][0] = 1;
    for (int i = 1; i