普通母函数，模板题
本题要点：
1、用于多项式相乘的两个数组 sup 和 tmp, 开到 5k
2、用一个变量标记 last 已经处理完的多项式，系数不等于0 的最大次数。
不用每次都要遍历到第 m 项（m项的系数就是答案）
3、 其他的套用母函数的模板。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 110, mod = 10000;
int n, sup[5000], tmp[5000], num[MaxN], value[MaxN];
int m;void solve()
{
memset(tmp, 0, sizeof tmp);memset(sup, 0, sizeof sup);sup[0] = 1;int last = 0;for(int i = 1; i <= n; ++i) //n条多项式{
for(int j = 0; j <= last; ++j){
for(int k = 0; k <= num[i] && k <= m; ++k){
if(k * value[i] + j <= m){
last = last > k * value[i] + j ? last : k * value[i] + j;tmp[k * value[i] + j] += sup[j];tmp[k * value[i] + j] %= mod;}}}for(int j = 0; j <= last; ++j){
sup[j] = tmp[j];}memset(tmp, 0, sizeof tmp);}if(sup[m] == 0){
printf("sorry\n");}else{
printf("%d\n", sup[m]);}
}int main()
{
int sum = 0;while(scanf("%d", &n) != EOF && n){
sum = 0;for(int i = 1; i <= n; ++i){
scanf("%d%d", &value[i], &num[i]);sum += value[i] * num[i];}if(sum % 3){
printf("sorry\n");continue;}m = sum / 3;solve();}return 0;
}/* 2 1 1 2 1 0 *//* 1 */