C 栗酱的数列 kmp结论题 模运算移项差分

 链接：https://ac.nowcoder.com/acm/contest/27589/C
来源：牛客网

题目描述

栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A’，
满足(a’₁+b₁)%k = (a’₂+b₂)%k = …… = (a’_m + b_m)%k。

输入描述:

第一行一个数T，表示有T组数据。
对于每组数据，
第一行三个整数，n, m, k。
第一行输入n个数, a₁,a₂,…,a_n, 表示A数列中的数，
第二行输入m个数, b₁,b₂,…,b_m, 表示B数列中的数。

输出描述:

每一组数据输出一行，满足条件的连续子序列数量。

示例1

输入

复制 2<br />3 2 5<br />7 8 7<br />8 7<br />3 2 5<br />7 8 9<br />8 7

2
3 2 5
7 8 7
8 7
3 2 5
7 8 9
8 7

输出

复制 1<br />2

1
2

备注:

T≤15,
2≤m≤n≤2×10⁵,
1≤a_i,b_i,k≤10⁹

分析：

%运算是可以满足结合律的

移项就变成了差分运算

只要存在 (a[i] – a[i+1]) % k == -(b[i] – b[i+1) % k 就行了

在a的差分数组里kmp b的差分数组 

//-------------------------代码----------------------------

//#define int ll
const int N = 3e6+10,base = 1e9+10;
int n,m,k;
int a[N],b[N];
int ca[N],cb[N];
int ha[N],hb[N];
int nxt[N];

void solve()
{
//    cin>>n>>m;
    cin>>n>>m>>k;
    fo(i,1,n) a[i] = b[i] = nxt[i] = 0;
    fo(i,1,n) cin>>a[i],a[i] %= k;
    fo(i,1,m) cin>>b[i],b[i] %= k;
    fo(i,1,n-1) a[i] = (a[i+1] - a[i] + k) % k;
    fo(i,1,m-1) b[i] = (b[i] - b[i+1] + k) % k;
    n -- ,m -- ;
    fo(i,2,m) {
        nxt[i] = nxt[i-1];
        while(nxt[i] && b[nxt[i] + 1] != b[i]) nxt[i] = nxt[nxt[i]];
        nxt[i] += (b[nxt[i] + 1] == b[i]);
    }
    fo(i,1,m) {
//         cout<<nxt[i]<<' ';
    }
//     cout<<endl;
    int j = 1,cnt = 0;
    fo(i,1,n) {
        while(j != 1 && b[j] != a[i]) j = nxt[j-1] + 1;
        if(a[i] == b[j]) j ++ ;
        if(j == m + 1) {
            cnt ++ ;
            j = nxt[j-1] + 1;
        }
    }
    cout<<cnt<<endl;
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------