双向dfs tle78pts求调教
查看原帖
双向dfs tle78pts求调教
754502
_AyachiNene楼主2023/12/3 15:02
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
inline int read()
{
	int res=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
	return res*f;
}
void write(int x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int n,m;
int x[114514],y[114514],fx,fy;
int ans[114514];
unordered_map<ll,vector<int> >mp;
void dfs1(int step,ll nx,ll ny,int cnt)
{
	if(step>n)
	{
		ll v=nx*1000000007+ny*998244353;
		mp[v].push_back(cnt);
		return;
	}
	dfs1(step+1,nx+x[step],ny+y[step],cnt+1);
	dfs1(step+1,nx,ny,cnt);
}
void dfs2(int step,ll nx,ll ny,int cnt)
{
	if(step>m)
	{
		ll v=nx*1000000007+ny*998244353;
		for(int i=0;i<mp[v].size();i++)
			++ans[mp[v][i]+cnt];
		return;
	}
	dfs2(step+1,nx-x[n+step],ny-y[n+step],cnt+1);
	dfs2(step+1,nx,ny,cnt);
}
int main()
{
	n=read(),fx=read(),fy=read();
	for(int i=1;i<=n;i++)
		x[i]=read(),y[i]=read();
	m=n;
	n/=2;
	m-=n;
	dfs1(1,0,0,0);
	dfs2(1,fx,fy,0);
	for(int i=1;i<=n+m;i++)
		write(ans[i]),puts("");
}
2023/12/3 15:02
加载中...