感觉这道题就是哈希乱搞可以过掉,题解区好像翻不到这个做法(
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int M=1e6+7,inf=0x3f3f3f3f,k=1e9+7,mxl=M/10;
int n,m,l,x,po[M],ha[M],ans1[M],ans2[M];
vector<int> a[M],len,b[M],pre[M],q[M];
unordered_map<int,int> cnt,inq,flag,fff;
bool ff;
void init(){
po[0]=1LL;
for(int i=1;i<=mxl;i++)po[i]=po[i-1]*k;
//cout<<po[mxl]<<endl;
}
void inpdata(int i){
scanf("%llu",&l);
for(int j=1;j<=l;j++){
scanf("%llu",&x);
if(x==0)x=114514;
a[i].push_back(x);
}
}
void inpdata2(int i){
scanf("%llu",&l);
for(int j=1;j<=l;j++){
//cout<<x<<endl;
scanf("%llu",&x);
if(x==0)x=114514;
b[i].push_back(x);
}
}
void to_cal_hash(int i){
int tmp=0LL;
for(int j=0;j<a[i].size();j++){
int x=a[i][j];
tmp+=x*po[j];
pre[i].push_back(tmp);
}
}
void to_cal_hash2(int i){
for(int j=0;j<b[i].size();j++)ha[i]+=b[i][j]*po[j];
}
int change(int sum,int r){
//cout<<sum<<" "<<mxl<<" "<<r<<" "<<po[mxl-r]<<endl;
return sum*po[mxl-r];
}
void solve(int ql){
for(int i=1;i<=n;i++){
flag.clear();
for(int l=0;l+ql-1<a[i].size();l++){
int r=l+ql-1,tmp;
//cout<<l<<" "<<ql<<" "<<a[i].size()<<endl;
if(l)tmp=change(pre[i][r]-pre[i][l-1],r+1);
else tmp=change(pre[i][r],r+1);
//if(i==2&&l==3)cout<<tmp<<endl;
//if(i==2&&l==3)cout<<change(ha[2],b[2].size())<<endl;
if(flag[tmp]||(!inq[tmp]))continue;
flag[tmp]=1;
cnt[tmp]++;
ans2[i]+=inq[tmp];
//cout<<i<<" "<<l<<" "<<r<<" "<<inq[tmp]<<endl;
//cout<<l<<" "<<r<<" "<<i<<endl;
}
}
}
signed main(){
scanf("%llu%llu",&n,&m);
init();
for(int i=1;i<=n;i++){
inpdata(i);
a[i].push_back(inf-i);
inpdata(i);
to_cal_hash(i);
//cout<<a[i].size()<<endl;
}
for(int i=1;i<=m;i++){
inpdata2(i);
if(!fff[l]){
len.push_back(l);
fff[l]=1;
}
q[l].push_back(i);
to_cal_hash2(i);
inq[change(ha[i],b[i].size())]++;
}
//cout<<pre[1][4]-pre[1][0]<<endl;
//cout<<ha[1]<<endl;
//cout<<change(ha[2],ll)<<endl;
int sum=0;
for(int i=0;i<len.size();i++){
cnt.clear();
solve(len[i]);
//ff=0;
for(int j=0;j<q[len[i]].size();j++){
int x=q[len[i]][j];
ans1[x]=cnt[change(ha[x],b[x].size())];
}
}
for(int i=1;i<=m;i++)sum+=ans1[i];
for(int i=1;i<=n;i++)sum-=ans2[i];
if(sum)printf("No\n");
//cout<<sum<<endl;
for(int i=1;i<=m;i++)printf("%llu\n",ans1[i]);
for(int i=1;i<=n;i++)printf("%llu ",ans2[i]);
return 0;
}
```cpp