The Balance(母函数)

The Balance

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7212    Accepted Submission(s): 2978

Problem Description

Now you are asked to measure a dose of medicine with a balance and a number of weights. Certainly it is not always achievable. So you should find out the qualities which cannot be measured from the range [1,S]. S is the total quality of all the weights.

 

Input

The input consists of multiple test cases, and each case begins with a single positive integer N (1<=N<=100) on a line by itself indicating the number of weights you have. Followed by N integers Ai (1<=i<=N), indicating the quality of each weight where 1<=Ai<=100.

 

Output

For each input set, you should first print a line specifying the number of qualities which cannot be measured. Then print another line which consists all the irrealizable qualities if the number is not zero.

 

Sample Input

3 1 2 4 3 9 2 1

 

Sample Output

0 2 4 5

 

题解：天平称药粉，为了这个题，我把母函数重刷了一遍，一遍A了；其实就是给一些钱，让计算在1~sum之间，有哪些钱不能被表示；sum等于给的Ai和；

我的思路是把所有的Ai再求一遍相反数，每个Ai有1个；

(1 + x^A[0])*(1 + x^A[1])*......*(1 + x^A[2 * n - 1]);

代码：

extern "C++"{
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
typedef long long LL;
typedef unsigned long long ULL;

void SI(int &x){scanf("%d",&x);}
void SI(double &x){scanf("%lf",&x);}
void SI(LL &x){scanf("%lld",&x);}
void SI(char *x){scanf("%s",x);}

}
const int MAXN = 10010;
int a[MAXN],b[MAXN];
int p[MAXN],m[MAXN];
int v[MAXN];
int ans[MAXN];
int main(){
    int N;
    while(~scanf("%d",&N)){
        int sum = 0;
        for(int i = 0;i < N; i++)scanf("%d",&v[i]),sum += v[i];
        for(int i = N ;i < 2*N ;i++){
            v[i] = -v[i - N];
        }
        N *= 2;
        mem(a,0);mem(b,0);
        a[0] = 1;a[v[0] ] = 1;
        for(int i = 1;i < N;i++){
            for(int j = 0;j <= sum;j++){
                for(int k = 0;k <= 1;k++){
                    if(j + k * v[i] < 0)
                        continue;
                    b[j + k * v[i] ] += a[j];
                }
            }
            for(int j = 0;j <= sum;j++){
                a[j] = b[j];b[j] = 0;
            }
        }
        int tp = 0;
        for(int i = 1;i <= sum;i++){
            if(!a[i])ans[tp++] = i;
        }
        printf("%d
",tp);
        if(!tp)continue;
        for(int i = 0;i < tp;i++){
            if(i)printf(" ");
            printf("%d",ans[i]);
        }
        puts("");
    }
    return 0;
}