方程的解数-MITM（折半搜索）-HASH

Description

　　已知一个n元高次方程： K1X1^P1+K2*X2P2+......KnXn^Pn 其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。假设未知数1≤ xi ≤M, i=1...n，1<=n<=6,m<=150求这个方程的整数解的个数。

Input

　　第1行包含一个整数n。
　　第2行包含一个整数M。
　　第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。
　　第3行的数据对应i=1，第n+2行的数据对应i=n。

Output

　　输出仅一行，包含一个整数，表示方程的整数解的个数

Sample Input

3
150
1 2
-1 2
1 2

Sample Output

178

---

思路

• 分别搜索前后两部分（折半搜索），加上hash
• 数组开够

---

代码

#include <iostream>
#include <cstdio>
#define hash 1000023
using namespace std;
int n,m,p[10],k[10],flag,ans,cnt,head[4000024];
struct fdfdfd{int next,to,num;}a[4000024];
int hhash(int x){return (x+hash)%hash;}
void addedge(int x)
{
	int y=hhash(x);
	for(int i=head[y];i;i=a[i].next)
	{
		int j=a[i].to;
		if(j==x){++a[i].num; return;}
	}
	a[++cnt].to=x; a[cnt].num=1; a[cnt].next=head[y]; head[y]=cnt;
}
int query(int x)
{
	int y=hhash(x);
	for(int i=head[y];i;i=a[i].next)
	{
		int j=a[i].to;
		if(j==x) return a[i].num;
	}
	return 0;
}
void dfs(int sta,int end,int sum)
{
	if(sta==end+1)
	{
		if(flag==0) addedge(sum);
		else ans+=query(-sum);
		return;
	}
	for(int i=1;i<=m;++i)
	{
		int temp=1;
		for(int j=1;j<=p[sta];++j) temp*=i;
		dfs(sta+1,end,sum+temp*k[sta]);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d%d",&k[i],&p[i]);
	flag=0; dfs(1,n/2,0);
	flag=1; dfs(n/2+1,n,0);
	printf("%d
",ans);
	return 0;
}