#P9027. [2017年备战省选]fibonacci

    ID: 9233 传统题 5000ms 888MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000省选/NOI-阈值划分大小情况后缀自动机按长度传播出现次数子树转区间一维前缀和时间戳避免清空数组复制数组处理环扩展 KMP差分标记区间修改线性递推

[2017年备战省选]fibonacci

题目描述

给定两个非空字符串 S1,S2S_1,S_2。对每个整数 i>2i>2,定义 Si=Si−1+Si−2S_i=S_{i-1}+S_{i-2},其中 ++ 表示按给出的顺序拼接。

如果一个字符串可以通过循环移位变成另一个字符串,就称这两个字符串等价。等价的两个字符串具有相同的最小循环表示。

有 QQ 次询问。每次给出一个正整数 idid 和一个非空字符串 TT,求 SidS_{id} 中有多少个与 TT 等价的子串。按子串的起始位置计数,可以重叠。即使 TT 的多个循环移位得到同一个字符串,同一个起始位置也只计一次。

输入格式

第一、二行分别输入字符串 S1,S2S_1,S_2。

第三行输入一个整数 QQ。

接下来 QQ 行,每行输入一个整数 idid 和一个字符串 TT。

输出格式

输出 QQ 行。每行输出对应答案对 998244353998244353 取模的结果。取模规则依据本站原有评测补入。

样例

a
b
5
1 a
1 b
5 ab
5 c
5 abba
1
0
3
0
1

数据范围

所有字符串均由小写英文字母组成。记 MM 为所有询问串的长度之和。对全部数据,1≤∣S1∣,∣S2∣≤1041\le |S_1|,|S_2|\le10^4,1≤Q≤1051\le Q\le10^5,1≤id≤10181\le id\le10^{18},1≤M≤1071\le M\le10^7。

原赛测试点 ∣S1∣,∣S2∣\lvert S_1\rvert,\lvert S_2\rvert QQ idid 上限 MM 上限
1 均为 11 ≤10\le10 2020 10410^4
2 ≤5\le5 ≤100\le100
3 ≤10\le10 =1=1 100100 10510^5
4~5 ≤105\le10^5
6 ≤103\le10^3 =1=1 10410^4 10610^6
7~9 ≤103\le10^3
10~12 ≤104\le10^4
13~15 ≤104\le10^4 ≤105\le10^5 10510^5 10710^7
16~20 101810^{18}

原赛样例 2、3 见当时下发的 fibonacci2.in/ans 与 fibonacci3.in/ans。

原题 PDF