6538: String
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：15
解决：3
题目描述
There is a string of length n, S[l..r] represents the string concatenated from the lth character to the rth character, and Slen is the length of the string(S[1..Slen] represents the whole S string).
We define FG as the number of positive integers x that satisfy the following conditions:
1. 1≤x≤Glen
2. G[1,x]=G[Glen−x+1,Glen]
3. The length of the common part of the intervals [1,x] and [Glen−x+1,Glen] is greater than 0 and is divisible by k.
Now ask for the value of ∏ni=1(FS[1..i]+1) modulo 998244353.
We define FG as the number of positive integers x that satisfy the following conditions:
1. 1≤x≤Glen
2. G[1,x]=G[Glen−x+1,Glen]
3. The length of the common part of the intervals [1,x] and [Glen−x+1,Glen] is greater than 0 and is divisible by k.
Now ask for the value of ∏ni=1(FS[1..i]+1) modulo 998244353.
输入
The first line of input is a positive integer T(T≤10) representing the number of data cases.
For each cases:
first line input a string S of lowercase letters, no longer than 106.
second line input a positive integer k(1≤k≤Slen).
For each cases:
first line input a string S of lowercase letters, no longer than 106.
second line input a positive integer k(1≤k≤Slen).
输出
For each cases, output a line with a positive integer representing the answer.
样例输入 复制
1
abababac
2
样例输出 复制
24提示
Note that the stack space of the judge system is a bit small, please pay attention to the reasonable allocation of memory.