P2603 解题报告
前言
挺有意思的一道题，但是因为我不会向量而止步。
建议先自己画图思考一二。
思路分析
看到题意的时候就感觉很烦。
下面简称题目中所说的
首先关注到的事操作里有个翻转，也就是沿
先考虑把这个操作拆出去，直接把轨迹根据
但这样可能会产生重复，暂且先不考虑，合并入如何判断两段轨迹相似。
不难发现，不管如何旋转，平移，线段的长度和线段间的夹角大小是不会改变的。
所以考虑通过线段长度和线段间夹角大小来判断相似。
又因为题目中还有缩放操作，所以我们用于比较的应该是线段长度间的比例而不是其长度。
这里就已经发现了一个比较难处理的东西：如何求线段间的夹角大小。
考虑向量：使用向量间的点积和叉积来等效替换线段间的夹角大小。
因为我们只考虑是否相等，所以直接表示判断即可，还可以避免精度问题。
而长度间比例如果考虑用浮点数存，可能也会有精度误差。
类似于上面的原因，因为只判重所以直接平方转化为分数即可（记得化为最简分数）。
接着考虑怎么找出现次数。
因为线段长度间的比例和线段间的夹角大小都是存在于线段之间的，所以若我们把一条线段看做一个点，上述两个东西便是存在于两点之间的边。
那这玩意又会联想到什么？
ACAM！
考虑把每一种轨迹都扔进 ACAM 里去，线段长度间的比例和线段间的夹角大小便成了 ACAM 里的转移状态函数。
考虑用 map 把这玩意存一下建出 ACAM。
又因为其中的字符集非常大，所以不能用正常的建 Fail 指针方法，只能采取暴力跳。
然后对于查询串一路在 ACAM 上跳查询即可。
而对于最前面的重复贡献问题，我们只需要在计算线段间的夹角大小时判断下与
实现的时候注意细节。笔者打错个数组名挂
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f3f3f3f3f,mod=998244353;
struct node{int a,b,c,d;bool operator<(const node&x) const{return (x.a^a)?a<x.a:(x.b^b)?b<x.b:(x.c^c)?c<x.c:d<x.d;}}a[N];
struct Point
{
int x,y;
inline Point operator-(const Point&a){return (Point){x-a.x,y-a.y};}
inline int operator*(const Point&a){return x*a.y-y*a.x;}
inline int operator^(const Point&a){return x*a.x+y*a.y;}
}s[N];
int n,m,inv[N],tag[N],ans[N];
struct ACAM
{
map<node,int>t[N];int tot=0,nxt[N],lst[N],cnt[N];vector<int>ed[N];
inline void insert(node s[],int n,int id)
{
int u=0;
for(int i=1;i<=n;i++)
{
auto v=t[u].find(s[i]);
if(v==t[u].end()) t[u][s[i]]=++tot,u=tot;
else u=v->second;
}
ed[u].emplace_back(id);
}
inline void build()
{
queue<int>q;for(auto v:t[0]) q.push(v.second);
while(!q.empty())
{
int u=q.front();q.pop();
for(auto [x,v]:t[u])
{
int f=nxt[u];
for(;f&&t[f].find(x)==t[f].end();f=nxt[f]);
if(t[f].find(x)!=t[f].end()) f=t[f][x];nxt[v]=f;
lst[v]=ed[f].empty()?lst[f]:f;q.push(v);
}
}
}
inline void solve()
{
int u=0;
for(int i=1;i<n-1;i++)
{
int v=u;
for(;v&&t[v].find(a[i])==t[v].end();v=nxt[v]);
if(t[v].find(a[i])!=t[v].end()) v=t[v][a[i]];u=v;
for(;v;v=lst[v]) cnt[v]++;
}
}
}ac;
namespace fast_IO
{
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read()
{
int x(0),t(1);char fc(getchar());
while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
return x*t;
}
inline void print(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
inline bool chk(char c) { return !(c>='A'&&c<='Z'); }
inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
inline void rd(char s[],int&n)
{
s[++n]=getchar();
while(chk(s[n])) s[n]=getchar();
while(ck(s[n])) s[++n]=getchar();
n--;
}
}using namespace fast_IO;
inline node tran(Point a,Point b,Point c)
{
node res;res.a=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
res.b=(b.x-c.x)*(b.x-c.x)+(c.y-b.y)*(c.y-b.y);
res.c=(c-b)*(b-a);res.d=(c-b)^(b-a);
int gcd=__gcd(res.a,res.b);res.a/=gcd,res.b/=gcd;
gcd=__gcd(abs(res.c),abs(res.d));res.c/=gcd;res.d/=gcd;return res;
}
signed main()
{
n=read(),m=read();
for(int i=1,k,f;i<=m;i++)
{
k=read();f=0;for(int j=1;j<=k;j++) s[j].x=read(),s[j].y=read();
for(int j=2;j<k;j++) a[j-1]=tran(s[j-1],s[j],s[j+1]),f|=bool(a[j-1].c);inv[i]=(!f)+1;
if(k<3) tag[i]=k;else ac.insert(a,k-2,i);
}ac.build();
for(int i=1;i<=n;i++) s[i].x=read(),s[i].y=read();
for(int i=2;i<n;i++) a[i-1]=tran(s[i-1],s[i],s[i+1]);
ac.solve();for(int i=1;i<=n;i++) s[i].x*=-1;
for(int i=2;i<n;i++) a[i-1]=tran(s[i-1],s[i],s[i+1]);ac.solve();
for(int i=1;i<=ac.tot;i++) for(auto v:ac.ed[i]) ans[v]+=ac.cnt[i]/inv[v];
for(int i=1;i<=m;i++) print(tag[i]?n-tag[i]+1:ans[i]),puts("");
return 0;
}