[ NOI 2001 ] 方程的解数

\(\\\)

\(Description\)

已知一个 \(N\) 元高次方程：

\[k_1x_1^{p_1}+k_2x_2^{p_2}+...+k_nx_n^{p_n}=0
\]

要求所有的 \(x_i\) 取值范围为\([1,m]\)且为整数，求方程的解数。

\(n\le 6,m\le 150\)

\(\\\)

\(Solution\)

发现 \(150^6\) 复杂度爆炸，自然能想到折半搜。

先搜前一半的所有可能的答案，存进哈希表里，然后搜后一半的答案，在哈希表里查相反数，如果存在就累加上个数。

然后 \(map\) 就被卡 \(T\) 了。其实这篇题解是哈希表学习笔记......

哈希表可以理解为一种类似多头链表的结构。当答案很大但是答案的个数并不是很多的时候选择。

每次得到一个答案先将他缩小在\([1,mod]\)范围内，然后查询这个值是否有存储过，如果有就累加计数器。

如果没有的话操作就很有意思了。考虑到可能会有多个数经过模运算得到的答案相同，所以不能直接在模运算所得答案处存储这个数，而要像邻接表一样，由这个答案向真正的数连一条边，边权就是个数。

然后查值得时候操作就和遍历邻接表一样了。因为模数选择质数，所以得到的答案分布还是很均匀的，单次查询和累加复杂度都接近\(\text 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\n",ans);

  return 0;

}

巴特西

[ NOI 2001 ] 方程的解数

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章