2022 Hangzhou Electric Multi-School 1st Session 01

题意：设F(i)表示sA prefix for the string[1…i]The intersection length of all intervals in k的倍数的boardnumber of strings,求${\prod }_{i=1}^{|s|}(f(i)+1)$
做法：z函数,差分
先求出s串的z函数(exkmp),设z[i]表示s串的z函数.Each prefix can be usedboardConvert each suffix to the prefix of the original stringlcp,Consider each suffix[i…n]的贡献,

画个图,容易发现当z[i]>=i时,At this time this suffix is ​​the same as the original stringlcppart only contributes.
此时第2*(i-1)+k,2*(i-1)+2k,2*(i-1)+3k…Every prefix can count towards this part of the contribution.Just make a difference,But distance isk.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x7f7f7f7f7f7f7f7f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define ldb long double
const int N=2e6+5;
const int mod=998244353;
const double eps=1e-8;
ll nxt[N];
void qnxt(char *c){
    
    int len = strlen(c);
    int p = 0, k = 1, l; 
    nxt[0] = len; 
    while(p + 1 < len && c[p] == c[p + 1]) p++;
    nxt[1] = p; 
    for(int i = 2; i < len; i++){
    
        p = k + nxt[k] - 1; 
        l = nxt[i - k]; 
        if(i + l <= p) nxt[i] = l; 
        else{
    
            int j = max(0ll, p - i + 1ll);
            while(i + j < len && c[i + j] == c[j]) j++; 
            nxt[i] = j;
            k = i; 
        }
    }
}
int lb,tag[N];
char  b[N];
ll ans;
signed main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif 
    IOS;
    int T;cin>>T;
    while( T-- ){
    
       cin >> b;
       int k;cin>>k;
       qnxt(b);
       lb = strlen(b);
       //枚举以i开始的后缀,Contribution difference
       for(int i=0 ;i<lb ;i++){
    
            int X = nxt[i];
            int id = i+1;//真实下标
            //Find the far left and the far rightpre[1...i]算贡献
            if( X>=id && X-id+1 >= k){
    
                tag[2*(id-1) + k]++;//左
                int t = (X-id+1)/k*k;
                if( 2*(id-1) + t + k <= lb ) tag[2*(id-1) + t + k]--;
            }
        }
       int ans=1;
       _for(i,1,lb){
    
            if( i-k>=1) tag[i] = tag[i] + tag[i-k];
            ans = ans * (tag[i]+1)%mod;
       }
       cout<<ans<<endl;
       _for(i,0,lb+k){
    
            tag[i]=0;
       }
    }
    return 0;
}