题解 | #栗酱的数列#

转化题目条件即可：

(a[i]+b[i])%k = (a[j]+b[j])%k

(b[i]-b[j])%k = (a[j]-a[i])%k（转化成了差分数组，第一项无用）

到这里就是正常kmp了

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int> a(n,0),b(m,0),A(n,0),B(m,0),nex(m,0);
    for(int i=0;i<n;i++){
        cin>>A[i];
        if(i)a[i-1]=((A[i]-A[i-1]+k)%k+k)%k;//注意+k，为了使余数都为正；i的判断条件可以去掉首项，没用
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
        if(i)b[i-1]=((B[i-1]-B[i])%k+k)%k;
    }
    
    //kmp算法
    for(int i=1;i<m-1;i++){
        int j=nex[i-1];
        while(b[i]!=b[j]&&j>0)j=nex[j-1];
        if(b[i]==b[j])j++;
        nex[i]=j;
    }
    int j=0,sum=0;
    for(int i=0;i<n-1;i++){
        while(a[i]!=b[j]&&j>0)j=nex[j-1];
        if(a[i]==b[j])j++;
        if(j==m-1){
            j=nex[j-1];
            sum++;
        }
    }
    
    cout<<sum<<'\n';
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}