暂无测试数据。

Description

方程的解数（NOI2001第二试，陕西•西安）
equation
问题描述：
　　已知一个n元高次方程：

　　其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。假设未知数1≤ xi ≤M, i=1,2,3,...,n，求这个方程的整数解的个数。

Input

　　文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。

Output

　　文件仅一行，包含一个整数，表示方程的整数解的个数。

Sample Input

3
150
1 2
-1 2
1 2

Sample Output

178

Limitation

1s, 65536KiB for each test case.

Hint

　　约束条件：
　　　　1 <= n <= 6；1 <= M <= 150；

　　　　方程的整数解的个数小于2^31。
　　　　★本题中，指数Pi(i=1,2,……,n)均为正整数。

　　[分析]
　　================================================================================================
　　这个是 NOI 2001 的第二试中的《方程的解数》一题，初看此题，题目要求出给定的方程解的个数，这个方程在最坏的情况下可以有6个未知数，而且次数由输入决定。这样就不能利用数学方法直接求出解的个数，而且注意到解的范围最多150个数，因此恐怕只能使用枚举法了。最简单的思路是穷举所有未知数的取值，这样时间复杂度是 O(M^6) ，无法承受。因此我们需要寻找更好的方法，自然想到能否缩小枚举的范围呢？但是发现这样也有很大的困难。我们再次注意到M 的范围，若想不超时，似乎算法的复杂度上限应该是 O(M^3) 左右，这是因为 150^3 < 10000000 。这就启示我们能否仅仅通过枚举3个未知数的值来找到答案呢？如果这样，前一半式子的值 S 可以确定，这时只要枚举后3 个数的值，检查他们的和是否等于-S 即可。这样只相当于在 O(M^3) 前面加了一个系数，当然还需要预先算出 1 到 150 的各个幂次的值。想到了这里，问题就是如何迅速的找到某个 S 是否曾经出现过，以及出现过了多少次，于是又变成了"某个元素是否在给定集合中"这个问题。所以，我们还是使用哈希表解决这个问题。至于哈希函数不是问题，还是把 S 的值作为关键字使用除余法即可。然而有一点需要注意，这个例子我们不仅需要纪录某个 S 是否出现，出现的次数也很重要，所以可以用一个2维数组，仅仅是加了一个存储出现次数的域而已。

Var
　　e:array[0..max-1,1..2]of longint;
　　//e[x,1] 记录哈希函数值为 x 的 S 值， e[x,2] 记录个 S 值出现了几次。因此 insert 过程也需要一些变化：
procedure ins(x:longint);
　var posi:longint;
begin
　　posi:=locate(x);
　　e[posi,1]:=x;
　　inc(e[posi,2]); {仅仅这一条语句，就可以记录下来 S 出现了几次}
end;

　　==================================================================================================

Source

GZOJ 1543