HDU1709

/*
该题使用的母函数有点特殊 因为x的次数可以为负
如测试数据
3
1 2 9
可以使用这样的母函数：(1+x+x^-1)*(1+x^2+x^-2) *(1+x^9+x^-9) ,
根据天枰的特点可以建模成像这样的母函数。
而算的时候是计算 (1+x+x^2)*(1+x^2+x^2) *(1+x^9+x^18)/(^1*x^2*x^9 ),
在该结果中大于0的指数中找 哪些指数的系数是0
*/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define M 10000
#define N 100
#define MS(x) memset(x,0,sizeof(x))
int n,sum;
int c1[M+1],c2[M+1];
int num[M+1],val[N+1];
void solve()
{
    MS(c1);
    MS(c2);
    int i,j,k;
    for(i=0;i<=val[1]*num[val[1]];i+=val[1])
        c1[i]=1;
    for(i=2;i<=n;++i)
    {
        for(j=0;j<=sum;++j)
        {
            for(k=0;k+j<=sum&&k<=val[i]*num[val[i]];k+=val[i])
            {
                 if(k>=j)c2[k-j]+=c1[j];
                    else  c2[j-k]+=c1[j];
                 c2[j-k]+=c1[j];
                 c2[k+j]+=c1[j];
            }
        }
        for(j=0;j<=sum;++j)
        {
            c1[j]=c2[j];
            c2[j]=0;
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        MS(num);
        MS(val);
        sum=0;
        int i;
        for(i=1;i<=n;++i)
        {
            scanf("%d",&val[i]);
            sum+=val[i];
            num[val[i]]=1;
        }
        solve();
//        for(i=1;i<=sum;++i)
//        printf("%d ",c1[i]);
//        printf("\n");
        int k=0;
        MS(num);
        for(i=1;i<=sum;++i)
        {
            if(!c1[i])
                num[k++]=i;
        }
        if(!k)
            printf("0\n");
        else
        {
            printf("%d\n",k);
        for(i=0;i<k;++i)
            printf("%d%c",num[i],i==k-1?'\n':' ');
        }
    }
 //   cout << "Hello world!" << endl;
    return 0;
}