【MX-X1-T4】「KDOI-05」简单的字符串问题

Luogu

IDLGP10716

Time2000ms

Memory512MB

DifficultyP6

字符串倍增树上启发式合并O2优化KMP 算法梦熊比赛

你有一个字符串 $S$。$q$ 个询问，每次给出 $(i,k)$，求有多少个非空字符串 $A$，使得存在可空字符串 $B_1,B_2,\dots,B_{k-1}$ 满足： $$S[1,i]=AB_1AB_2A\dots AB_{k-1}A$$ 其中 $S[1,i]$ 表示 $S$ 的长度为 $i$ 的前缀。 ## Input 第一行一个正整数 $n$ 表示 $S$ 的长度。接下来一个长度为 $n$ 且仅包含小写字母的字符串表示 $S$。接下来一行一个正整数表示 $q$。接下来 $q$ 行，每行两个正整数表示一个询问的 $i,k$。 ## Output 输出 $q$ 行，每行一个非负整数表示答案。 [samples] ## Background 原题链接：<https://oier.team/problems/X1D>。 ## Note **【样例解释 \#1】** 对于第一次询问 $(5,3)$，可以取 $A=\texttt{a}$，$B_1=\varepsilon$，$B_2=\texttt{ba}$，其中 $\varepsilon$ 表示空串。可以证明有且仅有一个合法的 $A$。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 分值 | $n,q\leq$ | 特殊性质 | |:--:|:--:|:--:|:--:| | $1$ | $5$ | $500$ | 无 | | $2$ | $10$ | $5000$ | 无 | | $3$ | $10$ | $2\times10^5$ | $S$ 中字符从 $\tt a,b$ 中随机生成 | | $4$ | $20$ | $2\times10^5$ | 每个询问的 $k$ 相同 | | $5$ | $20$ | $5\times10^4$ | 无 | | $6$ | $35$ | $2\times10^5$ | 无 | 对于 $100\%$ 的数据：$1\leq k\leq i\leq n\leq 2\times 10^5$，$1\leq q\leq 2\times 10^5$，$s$ 仅包含小写字母。

Samples

Input #1

10
aabaacaaaa
5
5 3
5 2
6 1
10 4
10 5

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "【MX-X1-T4】「KDOI-05」简单的字符串问题",
    "description": {
      "content": "你有一个字符串 $S$。$q$ 个询问，每次给出 $(i,k)$，求有多少个非空字符串 $A$，使得存在可空字符串 $B_1,B_2,\\dots,B_{k-1}$ 满足： $$S[1,i]=AB_1AB_2A\\dots AB_{k-1}A$$ 其中 $S[1,i]$ 表示 $S$ 的长度为 $i$ 的前缀。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10716"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一个字符串 $S$。$q$ 个询问，每次给出 $(i,k)$，求有多少个非空字符串 $A$，使得存在可空字符串 $B_1,B_2,\\dots,B_{k-1}$ 满足：\n\n$$S[1,i]=AB_1AB_2A\\dots AB_{k-1}A$$\n\n其中 $S[1,i]$ 表示 $S$ 的长度为 $i$ 的前缀。\n\n## Input\n\n第一行一个正整数 $n$ 表示 $S$ 的长度。\n\n接下来一个长...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments