「OICon-02」Native Faith

Luogu

IDLGP10176

Time3000ms

Memory1024MB

DifficultyP7

字符串后缀自动机 SAMO2优化分块AC 自动机根号分治

本题字符串下标从 $1$ 开始。定义两个字符串相加的结果为将这两个字符串首尾拼接形成的新字符串。令 $f(a,b,c)=\sum\limits_{i=1}^{|a|}\sum\limits_{j=i}^{|a|}\sum\limits_{k=1}^{|b|}\sum\limits_{l=k}^{|b|}[a_{i,i+1,\cdots,j}+b_{k,k+1,\cdots,l} = c]$（$a,b,c$ 均为字符串）。即有多少种方式从 $a,b$ 中分别选出一个非空子串使两个子串的和为 $c$。给定 $n$ 个字符串 $s_1,s_2,s_3,\cdots,s_n$。有 $q$ 次询问，每次询问给出三个正整数 $l,r,k$，求 $\sum\limits_{i=l}^r\sum\limits_{j=l}^rf(s_i,s_j,s_k)$。 ## Input 第一行包含两个整数 $n,q$。下面 $n$ 行，每行一个只包含小写字母的非空字符串表示 $s_1,s_2,\cdots,s_n$。下面 $q$ 行，每行三个正整数 $l,r,k$，表示一次询问。 ## Output 对于每个询问，每行输出一个整数表示答案。 [samples] ## Note ### 样例解释对于样例 $1$，给出部分 $f$ 函数的值。 - $f(s_1,s_1,s_3)=0$，$f(s_1,s_2,s_3)=1$，$f(s_1,s_3,s_3)=2$，$f(s_2,s_1,s_3)=1$，$f(s_2,s_2,s_3)=4$，$f(s_2,s_3,s_3)=7$，$f(s_3,s_1,s_3)=2$，$f(s_3,s_2,s_3)=7$，$f(s_3,s_3,s_3)=12$。 ### 数据范围 **本题采用捆绑测试。** 令 $m=\sum|s_i|$。 | $\text{Subtask}$ | 特殊性质 | $\text{Score}$ | | :-----------: | :-----------: | :-----------: | | $1$ | $1\le n,m,q\le 3\times 10^3$ | $17$ | | $2$ | 保证每次询问的 $k$ 各不相同 | $23$ | | $3$ | $1\le n,m,q\le 3\times 10^4$ | $27$ | | $4$ | 字符串只包含小写字母 $\texttt{a}$ | $19$ | | $5$ | 无特殊限制 | $14$ | 对于 $100\%$ 的数据：$1\le n,m,q\le 10^5$，$1\le l \le r\le n$，$1\le k\le n$，字符串仅包含小写字母。

Samples

Input #1

Output #1

6
30
36

Input #2

10 10
aabb
aba
abbba
abaccaab
abbba
ababababab
aaaaa
bbbbbb
aaba
abbba
1 10 10
1 4 5
3 6 4
2 8 1
1 5 4
2 10 7
2 9 2
4 5 5
5 5 6
8 9 10

Output #2

Input #3

5 5
a
ba
aba
ababa
abab
1 3 3
1 2 3
2 3 3
4 4 5
3 4 4

Output #3

API Response (JSON)

{
  "problem": {
    "name": "「OICon-02」Native Faith",
    "description": {
      "content": "本题字符串下标从 $1$ 开始。   定义两个字符串相加的结果为将这两个字符串首尾拼接形成的新字符串。 令 $f(a,b,c)=\\sum\\limits_{i=1}^{|a|}\\sum\\limits_{j=i}^{|a|}\\sum\\limits_{k=1}^{|b|}\\sum\\limits_{l=k}^{|b|}[a_{i,i+1,\\cdots,j}+b_{k,k+1,\\cdots,l} = c",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10176"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "本题字符串下标从 $1$ 开始。  \n\n定义两个字符串相加的结果为将这两个字符串首尾拼接形成的新字符串。\n\n令 $f(a,b,c)=\\sum\\limits_{i=1}^{|a|}\\sum\\limits_{j=i}^{|a|}\\sum\\limits_{k=1}^{|b|}\\sum\\limits_{l=k}^{|b|}[a_{i,i+1,\\cdots,j}+b_{k,k+1,\\cdots,l} = c...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments