(\)
(Description)
已知一个 (N) 元高次方程：
[k_1x_1^{p_1}+k_2x_2^{p_2}+...+k_nx_n^{p_n}=0
]
要求所有的 (x_i) 取值范围为([1,m])且为整数，求方程的解数。
- (nle 6,mle 150)
(\)
(Solution)
发现 (150^6) 复杂度爆炸，自然能想到折半搜。
先搜前一半的所有可能的答案，存进哈希表里，然后搜后一半的答案，在哈希表里查相反数，如果存在就累加上个数。
然后 (map) 就被卡 (T) 了。其实这篇题解是哈希表学习笔记......
哈希表可以理解为一种类似多头链表的结构。当答案很大但是答案的个数并不是很多的时候选择。
每次得到一个答案先将他缩小在([1,mod])范围内，然后查询这个值是否有存储过，如果有就累加计数器。
如果没有的话操作就很有意思了。考虑到可能会有多个数经过模运算得到的答案相同，所以不能直接在模运算所得答案处存储这个数，而要像邻接表一样，由这个答案向真正的数连一条边，边权就是个数。
然后查值得时候操作就和遍历邻接表一样了。因为模数选择质数，所以得到的答案分布还是很均匀的，单次查询和累加复杂度都接近( ext O(1))。
(\)
(Code)
#include<map>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define gc getchar
#define mod 6893911
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
int n,m,t[10],k[10],ans;
struct hashtable{
int hd[mod+2],tot;
struct edge{int w,to,nxt;}e[4000000];
inline void add(int u,int v){
e[++tot].to=v; e[tot].w=1;
e[tot].nxt=hd[u]; hd[u]=tot;
}
inline int find(int x){
int tmp=(x%mod+mod)%mod;
if(!hd[tmp]) return -1;
for(R int i=hd[tmp],v;i;i=e[i].nxt)
if((v=e[i].to)==x) return e[i].w;
return -1;
}
inline void insert(int x){
int tmp=(x%mod+mod)%mod;
if(!hd[tmp]) add(tmp,x);
else{
for(R int i=hd[tmp],v;i;i=e[i].nxt)
if((v=e[i].to)==x){++e[i].w;return;}
add(tmp,x);
}
}
}s;
inline int qpow(int x,int t){
int res=1;
while(t){
if(t&1) res*=x;
x*=x; t>>=1;
}
return res;
}
void dfsl(int p,int sum){
if(p>n/2){s.insert(sum);return;}
for(R int i=1;i<=m;++i) dfsl(p+1,sum+k[p]*qpow(i,t[p]));
}
void dfsr(int p,int sum){
if(p>n){
int tmp=s.find(-sum);
if(tmp>0) ans+=tmp; return;
}
for(R int i=1;i<=m;++i) dfsr(p+1,sum+k[p]*qpow(i,t[p]));
}
int main(){
n=rd(); m=rd();
for(R int i=1;i<=n;++i) k[i]=rd(),t[i]=rd();
dfsl(1,0); dfsr(n/2+1,0);
printf("%d
",ans);
return 0;
}