已知一個n元高次方程：

k1x1p1+k2x2p2+……+knxnpn = 0

其中：x1, x2, …,xn是未知數，k1,k2,…,kn是系數，p1,p2,…pn是指數。且方程中的所有數均為整數。

假設未知數1≤ xi ≤M, i=1,,,n，求這個方程的整數解的個數。

文件的第1行包含一個整數n。第2行包含一個整數M。第3行到第n+2行，每行包含兩個整數，分別表示ki和pi。兩個整數之間用一個空格隔開。第3行的數據對應i=1，第n+2行的數據對應i=n。

文件僅一行，包含一個整數，表示方程的整數解的個數。

3

150

1  2

-1  2

1  2

178

 1≤n≤6；1≤M≤150；

|k1Mp1|+|k2Mp2|+……+|knMpn |< 231

方程的整數解的個數小于231。

★本題中，指數Pi(i=1,2,……,n)均為正整數。

題解：dfs+hash

折半搜索，對于式子中的前一半爆搜出所有的值存入hash表中。

然后在搜索剩余一半的答案，判斷hash表中是否有能組合形成0的數，計算即可。

#include<iostream>  #include<cstring>  #include<cstdio>  #include<algorithm>  #include<cmath>  #define N 100  #define mod 7231773using namespace std;  struct data{	int val,num;}mp[mod+10];int n,m,cnt,t;  int k[N],p[N],mi[160][10];  int hash(int val){	int c=abs(val)%mod;	while (mp[c].num>0&&mp[c].val!=val) c=(c+1)%mod;	return c;}void dfs(int x,int sum){	if (x>t) {	   int pos=hash(sum);       mp[pos].val=sum; mp[pos].num++; 	   return;    }	for (int i=1;i<=m;i++)       dfs(x+1,sum+mi[i][p[x]]*k[x]);}void dfs1(int x,int sum){	if (x>n) {	  int pos=hash(-sum);	  cnt+=mp[pos].num;	  return;    }	for (int i=1;i<=m;i++) dfs1(x+1,sum+mi[i][p[x]]*k[x]);}int main()  {      freopen("equation1.in","r",stdin);      //freopen("equation1.out","w",stdout);      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++) {          mi[i][0]=1;          for (int j=1;j<=6;j++) mi[i][j]=mi[i][j-1]*i;      }      if (n==1) {          int ans=0;        for (int i=1;i<=m;i++) {              ans=mi[i][p[1]]*k[1]; 			//cout<<mi[i][p[1]]<<" "<<ans<<endl;             if (!ans) cnt++;          }          PRintf("%d/n",cnt);          return 0;      }      t=n/2;  dfs(1,0);    dfs1(t+1,0);    printf("%d/n",cnt);  }