[折半搜索][哈希]POJ1186方程的解数

题目传送门

这道题明显N数据范围非常小，但是M很大，所以用折半搜索实现搜索算法的指数级优化，将复杂度优化到O(M^(N/2))。

将搜出的两半结果用哈希的方式合并(乘法原理)。

Code：

#include <cstdio>

#include <algorithm>

#define Kss 10000000

using namespace std;

int N,hf,kl[],kr[],pl[],pr[],M;

int Gl[Kss],Gr[Kss],Cl,Cr;

int ksm(int x,int y){int Res=;while(y){if(y&)Res*=x;x*=x;y>>=;}return Res;}

void searchl(int x,int tot){

    if(x==hf+){Gl[++Cl]=tot;return ;}

    for(int i=;i<=M;i++)searchl(x+,tot+kl[x]*ksm(i,pl[x]));

}

void searchr(int x,int tot){

    if(x==N-hf+){Gr[++Cr]=tot;return ;}

    for(int i=;i<=M;i++)searchr(x+,tot+kr[x]*ksm(i,pr[x]));

}

int Ans=;

int hs[Kss],Cts[Kss];

void hash(int x){int k=x>?x:-x;k%=Kss;while(hs[k]!=x&&hs[k]!=-2e9)k=k%Kss+;hs[k]=x,Cts[k]++;}

int find(int x){int k=x>?x:-x;k%=Kss;while(hs[k]!=x&&hs[k]!=-2e9)k=k%Kss+;return Cts[k];}

int main()

{

    scanf("%d%d",&N,&M);

    for(int i=;i<Kss;i++)hs[i]=-2e9;

    hf=N>>;

    for(int i=;i<=hf;i++)scanf("%d%d",&kl[i],&pl[i]);

    for(int i=;i<=N-hf;i++)scanf("%d%d",&kr[i],&pr[i]);

    searchl(,),searchr(,);

    for(int i=;i<=Cr;i++)Gr[i]=-Gr[i];

    for(int i=;i<=Cl;i++)hash(Gl[i]);

    for(int i=;i<=Cr;i++)Ans+=find(Gr[i]);

    printf("%d",Ans);

    return ;

}