Analysis:This problem requires that we find the number of solutions to an equation.The equation is given as k
1*x
1^q
1+k
2*x
2^q
2+...+k
n*x
n^q
n=0,where n is within the range [1,6],x
i is within the range [1,150],and q
i 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 x
i 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 k
1*x
1^q
1+k
2*x
2^q
2+...k
i*x
i^q
i=-(k
i+1*x
i+1^q
i+1+k
i+2*x
i+2^q
i+2+...k
n*x
n^q
n).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 x
i 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 }