String
Time Limit : 3000/1500ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
There is a string of length $n$, $S[l..r]$ represents the string concatenated from the lth character to the rth character, and $S_{len}$ is the length of the string($S[1..S_{len}]$ represents the whole $S$ string).
We define $F_G$ as the number of positive integers x that satisfy the following conditions:
1. $1\leq x\leq G_{len}$
2. $G[1,x]=G[G_{len}-x+1,G_{len}]$
3. The length of the common part of the intervals $[1,x]$ and $[G_{len}-x+1,G_{len}]$ is greater than $0$ and is divisible by $k$.
Now ask for the value of $\prod_{i=1}^n (F_{S[1..i]}+1)$ modulo $998244353$.
We define $F_G$ as the number of positive integers x that satisfy the following conditions:
1. $1\leq x\leq G_{len}$
2. $G[1,x]=G[G_{len}-x+1,G_{len}]$
3. The length of the common part of the intervals $[1,x]$ and $[G_{len}-x+1,G_{len}]$ is greater than $0$ and is divisible by $k$.
Now ask for the value of $\prod_{i=1}^n (F_{S[1..i]}+1)$ modulo $998244353$.
Input
The first line of input is a positive integer $T(T\leq 10)$ representing the number of data cases.
For each cases:
first line input a string $S$ of lowercase letters, no longer than $10^6$.
second line input a positive integer $k(1 \leq k \leq S_{len})$.
For each cases:
first line input a string $S$ of lowercase letters, no longer than $10^6$.
second line input a positive integer $k(1 \leq k \leq S_{len})$.
Output
For each cases, output a line with a positive integer representing the answer.
Sample Input
1 abababac 2
Sample Output
24
Hint
Note that the stack space of the judge system is a bit small, please pay attention to the reasonable allocation of memory.
Source
2022“杭电杯”中国大学生算法设计超级联赛（1）