#1933. GDSOI2019 novel 加强版
GDSOI2019 novel 加强版
GDSOI2019 novel 加强版
题目描述
标题: GDSOI2019 novel 加强版 - Problem - QOJ.ac
#13457. GDSOI2019 novel 加强版
The problem was used in the following contests:
给定 n 个字符串 s1,s2,⋯,sn。每个字符串都有一个权值 wi。
记 S[l:r] 为字符串 S 从第 l 个字符到第 r 个字符构成的子串(下标从 1 开始),f(S,T) 为字符串 T 在字符串 S 中的出现次数。
记 g(S)=∑i=1nwi×f(S,si),h(S)=max1≤l≤r≤|S|g(S[l:r])r−l+1。
对于 ∀h(S)=ab,其中 a,b 的最大公约数为 1,规定 h^(S)=a⋅b−1mod998244353,其中 b−1 表示 b 在 mod998244353 意义下的乘法逆元。可以证明在本题遇到的所有情形中 b 均存在乘法逆元。
对于所有 1≤i≤n,1≤j≤|si|,请求出 h(si[1:j])。注意一些 subtask 仅需求出部分答案,详见输入输出格式。
输入格式
第一行包含两个整数 n,T,分别表示字符串数和该测试点类型。
接下来 n 行,每行一个字符串和一个正整数,分别表示 si 和 wi。
输出格式
对于 T=0 的subtask,请以浮点数形式输出 h(s1)。输出结果与标准输出的绝对误差在 10−4 之内即算正确。
对于 T=1 的subtask,为减少输出量,你只需输出 ⊕1≤i≤n,1≤j≤|si|h^(si[1:j]),其中 ⊕ 表示按位异或运算,亦即C++语言中的 ^ 运算符。
样例数据
样例 1 输入
4 0
ababcdcd 0
ab 12
abc 20
bc 15
样例 1 输出
15.666667
样例 2 输入
4 1
ababcdcd 0
ab 12
abc 20
bc 15
样例 2 输出
980069045
子任务
记 m=∑i=1n|si|,l=maxi=2n|si|。
subtask1(3pts): m,l≤50,T=1;
subtask2(14pts): m,l≤2000,T=1;
subtask3(19pts): m≤105,l≤50,T=0;
subtask4(23pts): m,l≤105,T=0;
subtask5(15pts): m,l≤3⋅105,T=0;
subtask6(26pts): m,l≤5⋅106,T=1;
对于所有测试点保证 1≤wi≤109,maxi=1ng(si)≤1018,|si|≥1,n≤2⋅105。
对于 T=0 的子任务保证答案绝对值属于区间 (1,108) 。
保证 si 仅由字符 a、b、c、d 构成。
系统支持 128 位整数。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 0
ababcdcd 0
ab 12
abc 20
bc 15
15.666667
样例 2
4 1
ababcdcd 0
ab 12
abc 20
bc 15
980069045