[SDOI/SXOI2022] 子串统计

Luogu

IDLGP8351

Time3000ms

Memory512MB

DifficultyP7

各省省选2022山东O2优化山西

小 D 四岁半的时候学会了后缀自动机。你有一个字符串 $S$，长度为 $n$。初始时，$T_0=S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i + 1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n - 1}$，根据每次删除的选择，一共有 $2^{n - 1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相同的串，但是我们仍然把它当成两种不一样的操作序列。对于一个串 $T$，我们记 $\operatorname{\textit{occ}}(T)$ 表示 $T$ 在 $S$ 中作为子串的出现次数，比如 $\operatorname{\textit{occ}}(\texttt{aaa},\texttt{aaaabaaa})=3$。对于一个操作序列，记它贡献是 $$\prod_{i = 1}^{n - 1} \operatorname{\textit{occ}}(T_i)$$ 求出所有操作序列的贡献和，由于答案很大，请输出答案对 $998244353$ 取模的结果。 ## Input 只有一行一个字符串 $S$，保证只包含小写字符。 ## Output 输出一行一个整数表示答案。 [samples] ## Note ### 数据规模与约定本题共 $20$ 个测试点。 - 对于测试点 $1\sim 5$，满足 $|S| \le 5000$。 - 对于测试点 $6\sim 8$，满足 $S$ 的每个字符均从 $\texttt a$ 和 $\texttt b$ 中等概率独立随机生成。 - 对于测试点 $9\sim 14$，满足 $|S| \le 6 \times 10^4$。对于所有数据，$1 \le |S| \le 10^5$。$S$ 中只有小写英文字母。

Samples

Input #1

zzz

Output #1

Input #2

abbab

Output #2

Input #3

见附加样例文件中的 ex_substring3.in

Output #3

见附加样例文件中的 ex_substring3.out

API Response (JSON)

{
  "problem": {
    "name": "[SDOI/SXOI2022] 子串统计",
    "description": {
      "content": "小 D 四岁半的时候学会了后缀自动机。 你有一个字符串 $S$，长度为 $n$。初始时，$T_0=S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i + 1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n - 1}$，根据每次删除的选择，一共有 $2^{n - 1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8351"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 D 四岁半的时候学会了后缀自动机。\n\n你有一个字符串 $S$，长度为 $n$。初始时，$T_0=S$。每次你可以从删除 $T_i$ 的开头或结尾的字符得到新的字符串 $T_{i + 1}$，经过 $n-1$ 次操作之后，我们会得到只有一个字符的串 $T_{n - 1}$，根据每次删除的选择，一共有 $2^{n - 1}$ 种可能的操作序列。注意，虽然可能会有一次操作，删除开头或结尾的字符得到相...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments