{"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接下来一个长度为 $n$ 且仅包含小写字母的字符串表示 $S$。\n\n接下来一行一个正整数表示 $q$。\n\n接下来 $q$ 行，每行两个正整数表示一个询问的 $i,k$。\n\n## Output\n\n输出 $q$ 行，每行一个非负整数表示答案。\n\n[samples]\n\n## Background\n\n原题链接：<https://oier.team/problems/X1D>。\n\n## Note\n\n**【样例解释 \\#1】**\n\n对于第一次询问 $(5,3)$，可以取 $A=\\texttt{a}$，$B_1=\\varepsilon$，$B_2=\\texttt{ba}$，其中 $\\varepsilon$ 表示空串。可以证明有且仅有一个合法的 $A$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 分值 | $n,q\\leq$ | 特殊性质 |\n|:--:|:--:|:--:|:--:|\n| $1$ | $5$ | $500$ | 无 |\n| $2$ | $10$ | $5000$ | 无 |\n| $3$ | $10$ | $2\\times10^5$ | $S$ 中字符从 $\\tt a,b$ 中随机生成 |\n| $4$ | $20$ | $2\\times10^5$ | 每个询问的 $k$ 相同 |\n| $5$ | $20$ | $5\\times10^4$ | 无 |\n| $6$ | $35$ | $2\\times10^5$ | 无 |\n\n对于 $100\\%$ 的数据：$1\\leq k\\leq i\\leq n\\leq 2\\times 10^5$，$1\\leq q\\leq 2\\times 10^5$，$s$ 仅包含小写字母。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10716","tags":["字符串","倍增","树上启发式合并","O2优化","KMP 算法","梦熊比赛"],"sample_group":[["10\naabaacaaaa\n5\n5 3\n5 2\n6 1\n10 4\n10 5","1\n2\n1\n2\n1"],["10\nbababababa\n10\n6 1\n6 2\n6 3\n6 4\n6 5\n10 2\n10 3\n9 4\n5 5\n4 2","1\n1\n1\n0\n0\n2\n1\n1\n0\n1\n"]],"created_at":"2026-03-03 11:09:25"}}