poj 1186 方程的解数【折半dfs+hash】

折半搜索，map会T所以用hash表来存状态

#include<iostream>

#include<cstdio>

#include<map>

using namespace std;

const int N=10,mod=739391;

int n,m,k[N],p[N],w,a[155][N],h[1000005],cnt;

long long ans;

map<int,int>mp;

struct qwe

{

	int ne,to,va;

}e[4000005];

void update(int x)

{//cerr<<x<<endl;

	int u=(x%mod+mod)%mod,fl=0;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to==x)

		{

			e[i].va++;//cerr<<e[i].va<<endl;

			fl=1;

			break;

		}

	if(!fl)

	{

		cnt++;

		e[cnt].ne=h[u];

		e[cnt].to=x;

		e[cnt].va=1;

		h[u]=cnt;

	}

}

int ques(int x)

{//cerr<<x<<endl;

	int u=(x%mod+mod)%mod;

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].to==x)

			return e[i].va;

	return 0;

}

int ksm(int a,int b)

{

	int r=1;

	while(b)

	{

		if(b&1)

			r=r*a;

		a=a*a;

		b>>=1;

	}

	return r;

}

void dfs(int w,int v)

{

	if(!w)

	{

		update(v);

		return;

	}

	for(int i=1;i<=m;i++)

		dfs(w-1,v+k[w]*a[i][w]);

}

void dfs2(int w,int v)

{

	if(!w)

	{

		ans+=ques(-v);

		return;

	}

	for(int i=1;i<=m;i++)

		dfs2(w-1,v+k[n-w+1]*a[i][n-w+1]);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d%d",&k[i],&p[i]);

	for(int i=1;i<=m;i++)

		for(int j=1;j<=n;j++)

			a[i][j]=ksm(i,p[j]);

	int w=n/2;

	dfs(w,0);

	dfs2(n-w,0);

	printf("%lld\n",ans);

	return 0;

}

巴特西

poj 1186 方程的解数【折半dfs+hash】

最新文章

热门文章