[后缀自动机]The 2021 ICPC Asia Shenyang Regional Contest M【String Problem】题解
题目概述String Problem解题报告首先很显然，对于前缀 $i$ ，答案一定是某一个位置到 $i$ 。用后缀数组可以做，但是思考起来比较麻烦。考虑后缀自动机，在建立后缀自动机的时候我们记...
[AC自动机+倍增]The 2021 China Collegiate Programming Contest (Harbin) L【Karshilov's Matching Problem】
题目概述Karshilov's Matching Problem解题报告首先不难想到对 $n$ 个匹配串建AC自动机，在 $fail$ 树上求和就可以得知匹配到 $p$ 点时的权值和。然后我们观...
[矩阵乘法+线段树]The 2021 ICPC Asia Nanjing Regional Contest E【Paimon Segment Tree】题解
题目概述Paimon Segment Tree解题报告首先肯定考虑离线，把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[0,x-1])$ 。然后我们按顺序...
[广义后缀自动机+二分]2021-2022 ACM-ICPC Brazil Subregional Programming Contest B【Beautiful Words】题解
题目概述Beautiful Words解题报告先把 $A$ 复制一份，令 $B_i=A[i-n+1,i]$ 。然后二分答案 $mid$ ，这样就只需要验证是否存在 $i\in[n,2n-1]$ ...
