自动搬运

查看原文

来自洛谷，原作者为

	Hoks end

搬运于2025-08-24 21:39:32，当前版本为作者最后更新于2024-03-26 20:51:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

挺有意思的一道题，但是因为我不会向量而止步。

建议先自己画图思考一二。

思路分析

看到题意的时候就感觉很烦。

下面简称题目中所说的 $Q$ 经过有限次的平移、旋转、翻转、放缩之后得到 $Q'$ 为 $Q$ 与 $Q'$ 相似。

首先关注到的事操作里有个翻转，也就是沿 $x$ 轴对称。

先考虑把这个操作拆出去，直接把轨迹根据 $x$ 轴对称一次。

但这样可能会产生重复，暂且先不考虑，合并入如何判断两段轨迹相似。

不难发现，不管如何旋转，平移，线段的长度和线段间的夹角大小是不会改变的。

所以考虑通过线段长度和线段间夹角大小来判断相似。

又因为题目中还有缩放操作，所以我们用于比较的应该是线段长度间的比例而不是其长度。

这里就已经发现了一个比较难处理的东西：如何求线段间的夹角大小。

考虑向量：使用向量间的点积和叉积来等效替换线段间的夹角大小。

因为我们只考虑是否相等，所以直接表示判断即可，还可以避免精度问题。

而长度间比例如果考虑用浮点数存，可能也会有精度误差。

类似于上面的原因，因为只判重所以直接平方转化为分数即可（记得化为最简分数）。

接着考虑怎么找出现次数。

因为线段长度间的比例和线段间的夹角大小都是存在于线段之间的，所以若我们把一条线段看做一个点，上述两个东西便是存在于两点之间的边。

那这玩意又会联想到什么？

ACAM！

考虑把每一种轨迹都扔进 ACAM 里去，线段长度间的比例和线段间的夹角大小便成了 ACAM 里的转移状态函数。

考虑用 map 把这玩意存一下建出 ACAM。

又因为其中的字符集非常大，所以不能用正常的建 Fail 指针方法，只能采取暴力跳。

然后对于查询串一路在 ACAM 上跳查询即可。

而对于最前面的重复贡献问题，我们只需要在计算线段间的夹角大小时判断下与 $x$ 轴对称后的轨迹是否相似即可。

实现的时候注意细节。笔者打错个数组名挂 $70$ 好久。

代码

#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;
}