CVBB ACM Team

• 日期：2020.7.13

• 比赛地址： 传送门

• 做题情况：lxh(-)，tyx(DF)，gyp(BJ)

给出$n$个字符串，定义函数$f(s,t)=i$，其中$i$是最大的自然数使得$s_{1 \ldots i} = t_{|t|-i+1 \ldots |t|}$，也就是说$s$的前缀和$t$的后缀相同，求$\sum_{i=1}^n \sum_{j=1}^n f(s_i,s_j)^2$，结果对998244353取模

$1 \le n \le 10^5$，$1 \le |s_i| \le 10^5$，$\sum |s_i| \le 10^6$

我们可以先用哈希把所有后缀的信息存下来，然后计算每一个前缀和多少个后缀相同，但是这样会计算除了答案的信息，例如字符串$aba$，其中前缀$a$和$aba$都被计算了一遍，所以我们需要去重。这里我们只需要对每一个字符串算出KMP算法中的$Next$值，然后令$cnt[Next[i]] -= cnt[i]$就可以计算答案了

给出一天内的两个时间，问中间差了多少秒

略

直接算出秒数然后求出差的绝对值即可

有一个$n \times n$的矩阵，其中$A_{ij} = lcm(i,j)$，现在给出$k$，要求这个矩阵中每个$k \times k$的矩阵种最大值的和

$1 \le n,m \le 5000$，$1 \le k \le min\{n,m\}$

求最大值可以直接二维单调队列用$O(nm)$的时间求出，瓶颈在于如何预处理，如果用$O(nm \log n)$的时间会超时，所以需要用递推的方式用$O(nm)$的时间求出gcd

第一小时：

第二小时：

第三小时：

第四小时：

第五小时：