链接
点击跳转
题解
把原来的式子移项，就得到
a
1
−
a
2
=
b
2
−
b
1
a_1-a_2=b_2-b1
a1−a2=b2−b1这样的式子，那么
(
−
a
1
)
−
(
−
a
2
)
=
b
1
−
b
2
(-a_1)-(-a_2) = b_1-b_2
(−a1)−(−a2)=b1−b2
所以先把第一个序列取相反数，然后直接转换成差分序列的子串匹配问题
k
m
p
kmp
kmp即可
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 400010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct KMP
{
int n
, next
[maxn
], t
[maxn
];
void build(ll
*r
, int len
)
{
int i
, j
=0;
n
=len
;
for(i
=1;i
<=len
;i
++)t
[i
]=r
[i
]; t
[len
+1]=0;
for(i
=2;i
<=len
;i
++)
{
for(;j
and t
[j
+1]!=t
[i
];j
=next
[j
]);
next
[i
] = t
[j
+1]==t
[i
]?++j
:0;
}
}
}kmp
;
ll a
[maxn
], b
[maxn
], r
[maxn
];
int main()
{
ll T
=read();
while(T
--)
{
ll n
=read(), m
=read(), k
=read(), i
, j
;
rep(i
,1,n
)a
[i
]=(k
-read()%k
)%k
;
rep(i
,1,m
)b
[i
]=read()%k
;
drep(i
,n
,1)a
[i
]=(a
[i
]-a
[i
-1]+k
)%k
;
drep(i
,m
,1)b
[i
]=(b
[i
]-b
[i
-1]+k
)%k
;
rep(i
,1,m
-1)r
[i
]=b
[i
+1]; r
[m
]=k
+5;
rep(i
,1,n
-1)r
[m
+i
]=a
[i
+1];
kmp
.build(r
,m
+n
-1);
ll ans
=0;
rep(i
,m
+1,m
+n
-1)ans
+=(kmp
.next
[i
]==m
-1);
printf("%lld\n",ans
);
}
return 0;
}
