#P12485. [2025年福建省队集训]字符串

    ID: 11648 传统题 4000ms 2048MiB 尝试: 6 已通过: 1 难度: 10 上传者: 标签>CF3400NOI/NOI+/CTSAC 自动机失败链接贡献汇总凸包双端队列消除被支配候选增量维护有理数精确运算逆元线性递推

[2025年福建省队集训]字符串

问题描述

给定 nn 个字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_n。每个字符串都有一个权值 wiw_i。

记 S[l:r]S[l:r] 为字符串 SS 从第 ll 个字符到第 rr 个字符构成的子串(下标从 11 开始),f(S,T)f(S,T) 为字符串 TT 在字符串 SS 中的出现次数。

记 g(S)=∑i=1nwi×f(S,si)g(S)=\sum_{i=1}^{n}w_i \times f(S,s_i),$h(S)=\max_{1 \le l \le r \le |S|}\frac{g(S[l:r])}{r-l+1}$。

对于 ∀h(S)=ab\forall h(S)=\frac{a}{b},其中 a,ba,b 的最大公约数为 1,规定 h^(S)=a⋅b−1 mod 998244353\hat{h}(S)=a \cdot b^{-1} \bmod 998244353,其中 b−1b^{-1} 表示 bb 在  mod 998244353\bmod 998244353 意义下的乘法逆元。

对于所有 1≤i≤n,1≤j≤∣si∣1 \le i \le n,1 \le j \le |s_i|,请求出 h(si[1:j])h(s_i[1:j])。注意一些 subtask 仅需求出部分答案,详见输入输出格式。

输入输出格式

输入格式

第一行包含两个整数 n,Tn,T,分别表示字符串数和该测试点类型。

接下来 nn 行,每行一个字符串和一个正整数,分别表示 sis_i 和 wiw_i。

输出格式

对于 T=0T=0 的 subtask,请以浮点数形式输出 h(s1)h(s_1)。输出结果与标准输出的绝对误差在 10−410^{-4} 之内即算正确。

对于 T=1T=1 的 subtask,为减少输出量,你只需输出 $\oplus_{1 \le i \le n,1 \le j \le |s_i|}\hat{h}(s_i[1:j])$,其中 ⊕\oplus 表示按位异或运算,亦即 C++ 语言中的 ^ 运算符。

样例

输入样例1

4 0

ababcdcd 0

ab 12

abc 20

bc 15

输出样例1

15.666667

数据范围

记 m=∑i=1n∣si∣,l=max⁡i=2n∣si∣m=\sum_{i=1}^{n}|s_i|,l=\max_{i=2}^{n}|s_i|。

子任务 分数 限制条件
1 3 m,l≤50m,l \le 50,T=1T=1
2 14 m,l≤2000m,l \le 2000,T=1T=1
3 19 m≤105,l≤50m \le 10^5,l \le 50,T=0T=0
4 23 m,l≤105m,l \le 10^5,T=0T=0
5 15 m,l≤3⋅105m,l \le 3 \cdot 10^5,T=0T=0
6 26 m,l≤5⋅106m,l \le 5 \cdot 10^6,T=1T=1

对于所有测试点保证:

  • 1≤wi≤1091 \le w_i \le 10^9
  • max⁡i=1ng(si)≤1018\max_{i=1}^{n}g(s_i) \le 10^{18}
  • ∣si∣≥1|s_i| \ge 1
  • n≤2⋅105n \le 2 \cdot 10^5
  • 对于 T=0T=0 的子任务保证答案绝对值属于区间 (1,108)(1,10^8)
  • 保证 sis_i 仅由字符 a、b、c、d 构成