题目描述
给定两个非空字符串 S1,S2。对每个整数 i>2,定义 Si=Si−1+Si−2,其中 + 表示按给出的顺序拼接。
如果一个字符串可以通过循环移位变成另一个字符串,就称这两个字符串等价。等价的两个字符串具有相同的最小循环表示。
有 Q 次询问。每次给出一个正整数 id 和一个非空字符串 T,求 Sid 中有多少个与 T 等价的子串。按子串的起始位置计数,可以重叠。即使 T 的多个循环移位得到同一个字符串,同一个起始位置也只计一次。
输入格式
第一、二行分别输入字符串 S1,S2。
第三行输入一个整数 Q。
接下来 Q 行,每行输入一个整数 id 和一个字符串 T。
输出格式
输出 Q 行。每行输出对应答案对 998244353 取模的结果。取模规则依据本站原有评测补入。
样例
a
b
5
1 a
1 b
5 ab
5 c
5 abba
1
0
3
0
1
数据范围
所有字符串均由小写英文字母组成。记 M 为所有询问串的长度之和。对全部数据,1≤∣S1∣,∣S2∣≤104,1≤Q≤105,1≤id≤1018,1≤M≤107。
| 原赛测试点 |
∣S1∣,∣S2∣ |
Q |
id 上限 |
M 上限 |
| 1 |
均为 1 |
≤10 |
20 |
104 |
| 2 |
≤5 |
≤100 |
| 3 |
≤10 |
=1 |
100 |
105 |
| 4~5 |
≤105 |
| 6 |
≤103 |
=1 |
104 |
106 |
| 7~9 |
≤103 |
| 10~12 |
≤104 |
| 13~15 |
≤104 |
≤105 |
105 |
107 |
| 16~20 |
1018 |
原赛样例 2、3 见当时下发的 fibonacci2.in/ans 与 fibonacci3.in/ans。
原题 PDF