#P14968. [2026年重庆省队集训]迁到题

    ID: 14184 传统题 2000ms 2048MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>CF2700回文树字符串哈希树状数组字符串数据结构数学Manacher

[2026年重庆省队集训]迁到题

题目描述

定义一个值域为 [1,n][1,n],长度分别为 k,nk,n 的数组对 (a,p)(a,p) 是好的,当且仅当:

  • ∀1≤i≤k,ak−i+1=pai\forall 1\leq i\leq k, a_{k-i+1} = p_{a_i}。

给你一个值域为 [1,n][1,n],长度为 nn 的数组 aa,对于 aa 的 n(n+1)2\frac{n(n+1)}2 个子段 a′a',以及 nnn^n 个值域为 [1,n][1,n],长度为 nn 的数组 pp,求出好的数组对 (a′,p)(a',p) 数量,对 998244353998244353 取模。

输入格式

第一行为一个正整数 nn,第二行 nn 个数为数组 aa。

输出格式

一行一个整数,代表好的数组对数对 998244353998244353 取模的结果。

样例输入 1

3
1 1 2

样例输出 1

39

样例输入 2

5
1 4 2 2 1

样例输出 2

4175

样例解释

对于第一个样例:

  • 有两个子段为 a′=[1]a'=[1],其有 99 个对应的好的 pp。
  • 有一个子段为 a′=[2]a'=[2],其有 99 个对应的好的 pp。
  • 有一个子段为 a′=[1,1]a'=[1,1],其有 99 个对应的好的 pp。
  • 有一个子段为 a′=[1,2]a'=[1,2],其有 33 个对应的好的 pp。
  • 有一个子段为 a′=[1,1,2]a'=[1,1,2],其有 00 个对应的好的 pp。

总共有 2×9+9+9+3+0=392\times9+9+9+3+0=39 个好的数组对 (a′,p)(a',p)。

数据范围

对于所有数据,

  • 1≤n≤1061\leq n\leq 10^6,
  • ∀1≤i≤n\forall 1\leq i\leq n,1≤ai≤n1\leq a_i\leq n。
子任务编号 n≤n\leq 特殊性质 分数 子任务依赖
11 77 - 55 -
22 300300 1010 11
33 40004000 A 55 -
44 - 1010 2,32,3
55 10510^5 A 33
66 - 2020 4,54,5
77 5×1055\times10^5 2525 66
88 10610^6 1515 77
  • 特殊性质 A:∀1≤i≤n\forall 1\leq i\leq n,ai=ia_i=i。

2s / 2048MB