不过一笑

Well life is tough,make a good laugh

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  8 Posts :: 0 Stories :: 1 Comments :: 0 Trackbacks

公告

This guy's no expert,he's just to build a solid foundation,that may turn out to be useful in the future

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Analysis:This problem requires that we find the number of solutions to an equation.The equation is given as k1*x1^q1+k2*x2^q2+...+kn*xn^qn=0,where n is within the range [1,6],xi is within the range [1,150],and qi is guaranteed to be positive integers.Besides,the number we're dealing with will not exceed the range of integer.
Naturally,we will try to enumerate all the possible values for xi and see if each of them satisfy the equation.However,this will cause us quite a lot of time.With a little improvement,we can move half of the items of the polynomial to the other side of the equation,and form a new one like k1*x1^q1+k2*x2^q2+...ki*xi^qi=-(ki+1*xi+1^qi+1+ki+2*xi+2^qi+2+...kn*xn^qn).With this equation at hand,all we need to do is to build a table of value of the left side and try to find out how many combinations of xi on the other side can make a value existing in the table we have.Consequently,we need the Hash table.The strategy we use here to deal with the collision would be to build a list on each node of the table.More details in the code.
Code:
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<vector>
  5 #define MAXSIZE 500050
  6 #define MOD 400037
  7 using namespace std;
  8 struct answer
  9 {
 10     int value,num;
 11     answer* next;
 12 }pool[MAXSIZE*4];
 13 answer *htable[MAXSIZE],*pp,*pt;
 14 answer* create(int value,int num,answer* temp)
 15 {
 16     pp->value=value;pp->num=num;
 17     pp->next=temp;return pp++;
 18 }
 19  
 20 int powers[151][6];
 21 int t[6],coe[6];
 22 int n,m,sum,counter;
 23 void init(int n,int m)
 24 {
 25     for(int i=1; i<=m; i++)
 26     {
 27         for(int j=0; j<n; j++)
 28         {
 29             powers[i][j]=(int)pow((double)i,t[j]);
 30         }
 31     }
 32 }
 33 void init_hash()
 34 {
 35     memset(htable,0,sizeof(htable));
 36     pp=pool;
 37 }
 38 void insert_hash(int sum)
 39 {
 40     int t=(sum>0? sum : (0-sum);t%=MOD;
 41     for(pt=htable[t];pt;pt=pt->next)
 42     {
 43         if(pt->value==sum)
 44         {
 45             pt->num++;
 46             return;
 47         }
 48     }
 49     htable[t]=create(sum,1,htable[t]);
 50 }
 51 void get_hash(int sum)
 52 {
 53     int t=(sum>0? sum : (0-sum);t%=MOD;
 54     for(pt=htable[t];pt;pt=pt->next)
 55     {
 56         if(pt->value==sum)
 57         {
 58             counter+=pt->num;
 59             return;
 60         }
 61     }
 62 }
 63 void dfs(int depth,int m)
 64 {
 65     if(depth==0)
 66     {
 67         insert_hash(sum);
 68         return;
 69     }
 70     for(int i=1; i<=m; i++)
 71     {
 72         int tp=(coe[depth-1]*powers[i][depth-1]);
 73         sum+=tp;
 74         dfs(depth-1,m);
 75         sum-=tp;
 76     }
 77 }
 78 void get_result(int d,int m)
 79 {
 80     if(!d)
 81     {
 82         get_hash(0-sum);
 83         return;
 84     }
 85     for(int i=1; i<=m; i++)
 86     {
 87         int tp=(coe[n-d]*powers[i][n-d]);
 88         sum+=tp;
 89         get_result(d-1,m);
 90         sum-=tp;
 91     }
 92 }
 93 int main()
 94 {
 95     int dp;
 96     while(scanf("%d",&n)==1)
 97     {
 98         scanf("%d",&m);
 99         for(int i=0; i<n; i++) scanf("%d%d",&coe[i],&t[i]);
100         if(n==1) printf("0\n");
101         else
102         {
103             init(n,m);
104             init_hash();
105             if(n==2) dp=1;
106             else if(n<6) dp=2;
107             else dp=3;
108  
109             sum=0;
110             dfs(dp,m);
111             sum=counter=0;
112             get_result(n-dp,m);
113             printf("%d\n",counter);
114         }
115     }
116 }


posted on 2010-10-04 18:37 雨过有声 阅读(355) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理