P5691 [NOI2001]方程的解数
题目传送门
分析：
题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有6个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且注意到解的范围最多150个数，因此恐怕只能使用枚举法了。
我一开始是先想到了用到dfs去穷举6层，虽然想法很美好，但是时间不允许啊O（mn）.换种思路， 题目要求n项值加起来=0，那我们可不可以只算n/2项呢？根据初中移项知识，就可以把题目变一个形式,前n/2项=-1*(后n/2项），那时间复杂度就降成O（mn>>1）,那这样就能过了。最后再用hash将前半段的值记录一下，然后在后半段搜索的时候看看与表中有多少个相同的就行了。
还有注意一下：
- 设前半段有3项，值可能为 1 2 3或3 2 1或2 1 3。虽然他们的总和是一样的，但是也算方程的不同解
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;
const int MAX=2147483647;
const int N=1e6;
const int Mod=10000007;
long long n,m,k[10],p[10],ans,mid;
long long hash[Mod+666][2];
long long qy(long long x) {return x%Mod;}
long long dw(long long x)
{long long a=qy(abs(x)),i=0;while(i<Mod&&hash[qy(a+i)][0]&&hash[qy(a+i)][0]!=x)i++;return qy(a+i);
}
void tp()
//特判，如果只有一个未知数，且系数为0，则方程正好有m组解(x=1..m)，否则无解
{if(n==1) {if(!k[1])printf("%lld",m);else printf("0");exit(0);}
}
void dfs1(long long dep,long long sum)//前半段
{if(dep==mid){//把所有可能出现的答案放进hashfor(long long i=1;i<=m;i++){long long temp=sum+k[dep]*pow(i,p[dep]);hash[dw(temp)][0]=temp,hash[dw(temp)][1]++;}return ;}for(long long i=1;i<=m;i++)dfs1(dep+1,sum+k[dep]*pow(i,p[dep]));
}
void dfs2(long long dep,long long sum)//后半段
{if(dep==n){for(long long i=1;i<=m;i++){long long temp=(-1)*(sum+k[dep]*pow(i,p[dep]));//记得要乘-1，移项变号if(hash[dw(temp)][0]==temp) ans+=hash[dw(temp)][1];//如果正好抵消，则加上其对应的数量}return ;}for(long long i=1;i<=m;i++)dfs2(dep+1,sum+k[dep]*pow(i,p[dep]));
}
int main()
{//fre();scanf("%lld%lld",&n,&m);mid=n>>1;for(int i=1;i<=n;i++) scanf("%lld%lld",&k[i],&p[i]);tp();dfs1(1,0),dfs2(mid+1,0);printf("%lld",ans);return 0;
}