分析：
首先(K+1)个位置的值才能确定一个次数为(K)的函数
所以如果(Kgeq n)直接输出0就好了，相当于我们要处理的(K)范围只有(10^5)
题解里面这个“两个序列相似的充要条件就是他们的特征序列相等”看不大懂
听了机房神仙的做法，NTT差分+KMP就能做
首先一个(K)次函数能算出来的连续(n)个值，差分(K+1)次得到的长度为(n-K-1)的序列必定全为0
可以理解为(K+1)次导数吧（？），不懂，数学只有小学水平
两个序列相减之后的差分序列全0，可以变换成两个序列先差分再相减序列全为0
相当于两个序列差分之后要相同
(B)要移位，老套路将(B)复制一份接到自己后面，差分之后KMP比较即可
(K+1)次暴力差分复杂度为(O(n^2))，考虑优化
列一下差分式子：
[b_i=sum_{j=0}^{K+1}(-1)^{K+1-j}inom{K+1}{j}a_{i+j}
]
这个是卷积形式，移下位用NTT算就行了
复杂度(O(nlogn))
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<string>
#define maxn 1000005
#define INF 0x3f3f3f3f
#define MOD 998244353
using namespace std;
inline int getint()
{
int num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int n,K;
int a[maxn],b[maxn];
int rev[maxn];
int fac[maxn],inv[maxn];
int fail[maxn];
inline int C(int p,int q)
{return 1ll*fac[p]*inv[q]%MOD*inv[p-q]%MOD;}
inline int ksm(int num,int k)
{
int ret=1;
for(;k;k>>=1,num=1ll*num*num%MOD)if(k&1)ret=1ll*ret*num%MOD;
return ret;
}
inline void NTT(int *a,int N,int opt)
{
for(int i=0;i<N;i++)if(rev[i]<i)swap(a[i],a[rev[i]]);
for(int i=1;i<N;i<<=1)
{
int wn=ksm(3,(MOD-1)/(i<<1));
if(!~opt)wn=ksm(wn,MOD-2);
for(int j=0;j<N;j+=i<<1)for(int k=0,w=1;k<i;k++,w=1ll*w*wn%MOD)
{
int x=a[j+k],y=1ll*w*a[i+j+k]%MOD;
a[j+k]=(x+y)%MOD,a[i+j+k]=(x-y+MOD)%MOD;
}
}
if(!~opt)for(int i=0,Inv=ksm(N,MOD-2);i<N;i++)a[i]=1ll*a[i]*Inv%MOD;
}
inline void solve(int *A,int N)
{
static int B[maxn];
int len=1;
while(len<=N+K)len<<=1;
for(int i=0;i<len;i++)rev[i]=(rev[i>>1]>>1)|(i&1?len>>1:0);
for(int i=0;i<=K;i++)B[i]=i&1?MOD-C(K,i):C(K,i);
for(int i=K+1;i<len;i++)B[i]=0;
NTT(A,len,1),NTT(B,len,1);
for(int i=0;i<len;i++)A[i]=1ll*A[i]*B[i]%MOD;
NTT(A,len,-1);
for(int i=0;i<N-K;i++)A[i]=A[i+K];
for(int i=N-K;i<len;i++)A[i]=0;
}
inline void getfail()
{
fail[0]=-1;
for(int i=1;i<n-K;i++)
{
int j=fail[i-1];
while(~j&&a[j+1]!=a[i])j=fail[j];
if(a[j+1]==a[i])fail[i]=j+1;
else fail[i]=-1;
}
}
int main()
{
n=getint(),K=getint();
for(int i=0;i<n;i++)a[i]=getint();
for(int i=0;i<n;i++)b[i]=b[i+n]=getint();
if((K++)>=n){printf("0
");return 0;}
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=K;i++)fac[i]=1ll*i*fac[i-1]%MOD;
for(int i=2;i<=K;i++)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=2;i<=K;i++)inv[i]=1ll*inv[i]*inv[i-1]%MOD;
solve(a,n);
solve(b,2*n);
getfail();
int tmp=-1;
for(int i=0;i<2*n-K;i++)
{
while(~tmp&&a[tmp+1]!=b[i])tmp=fail[tmp];
if(a[tmp+1]==b[i])tmp++;
if(tmp==n-K-1){printf("%d
",i-n+K+1);return 0;}
}
printf("-1
");
}
