母函数 HDU 1709 The Balance

这题大概意思是，给你n个砝码和一个天平，叫你找出从1 到 这n个砝码总和的范围内，找出不能称出的重量

可以套用母函数模板， 多项式相乘时，多了负指数。注意这题只是存在性，不需要求出每种重量的组合数，

直接标记就可以了。

还有一点需要注意，乘出来的多项式，负指数和正指数是相互对称的，只存其中一边即可

#include<iostream>
#include <math.h>
using namespace std;


int main()
{
        int a[10010];
        int positive[10010];
        int negative[10010];
        int num[120];
        int n;
        int hold;
        int maxindex;
        int firstboundary, secondboundary;
        int addnum;
        int counter;

        //freopen("C:\\Users\\Haojian\\Desktop\\test.txt", "r", stdin);

        while (cin >> n)
        {
                //数据初始化
                counter = 0;
                maxindex = 0;
                firstboundary = 0;

                for (int i = 0; i < 10010; i++)
                {
                        a[i] = 0;
                        positive[i] = 0;
                        negative[i] = 0;
                }

                cin >> hold;
                negative[hold] = 1;
                negative[0] = 1;
                num[0] = hold;
                maxindex = hold;
                positive[hold] = 1;
                positive[0] = 1;

                for (int i = 1; i < n; i++)
                {
                        cin >> hold;
                        num[i] = hold;                  
                        maxindex += hold;
                }

                //类似母函数模板
                for (int i = 2; i <= n; i++)
                {
                        //求2个上界
                        firstboundary = 0;
                        for (int k = i - 2; k >= 0; k--)
                                firstboundary += num[k];
                        
                        secondboundary = firstboundary + num[i - 1];
                        addnum = num[i-1];//当前乘的第i个多项式的每个项的指数每次增加的次数
                        
                        for (int j = -firstboundary; j <= firstboundary; j++)//从负数开始计算
                        {
                                if (negative[abs(j)])//negative数组是标记数组，记录目前求出的多项式是否有指数为j的项， 其下标是多项式项的指数
                                
                                for (int k = -addnum; k + j <= secondboundary && k <= num[i - 1]; k += addnum)//乘以下一个多项式
                                        if (k + j >= 0 )
                                        {
                                                positive[k+j] = 1;//记录可以称量的数目，positive数组下标是可以称量的数量
                                                a[k+j] = 1;
                                        }
                                        else
                                           a[-(k+j)] = 1;//记录乘出来的负指数的项                                  
                        }

                        //修改negative标记数组，重置a
                        for (int j = 0; j <= secondboundary; j++)
                        {
                                negative[j] = a[j];
                                a[j] = 0;
                        }
                        
                        
                }
                
                //输出
                for (int i = 0; i <= maxindex; i++)
                {
                        if (positive[i] == 0)
                                counter++;
                }
                
                cout << counter << endl;
                if (counter != 0)
                {       
                        for (int i = 1; i <= maxindex; i++)
                        {
                                if (positive[i] == 0 && counter > 1)
                                {
                                        cout << i << " ";
                                        counter--;
                                }
                                else

                                        if (positive[i] == 0 && counter == 1)
                                        {
                                                cout << i;
                                                break;
                                        }
                        }
                                cout << endl;
                }
        }

        return 0;
}