Rikka with Subset HDU

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: 

Yuta has nn positive A1−AnA1−An and their sum is mm. Then for each subset SS of AA, Yuta calculates the sum of SS. 

Now, Yuta has got 2n2n numbers between [0,m][0,m]. For each i∈[0,m]i∈[0,m], he counts the number of iis he got as BiBi. 

Yuta shows Rikka the array BiBi and he wants Rikka to restore A1−AnA1−An. 

It is too difficult for Rikka. Can you help her?  

InputThe first line contains a number t(1≤t≤70)t(1≤t≤70), the number of the testcases. 

For each testcase, the first line contains two numbers n,m(1≤n≤50,1≤m≤104)n,m(1≤n≤50,1≤m≤104).

The second line contains m+1m+1 numbers B0−Bm(0≤Bi≤2n)B0−Bm(0≤Bi≤2n).OutputFor each testcase, print a single line with nn numbers A1−AnA1−An. 

It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.Sample Input

2
2 3
1 1 1 1
3 3
1 3 3 1

Sample Output

1 2
1 1 1

        
 

Hint

In the first sample, $A$ is $[1,2]$. $A$ has four subsets $[],[1],[2],[1,2]$ and the sums of each subset are $0,1,2,3$. So $B=[1,1,1,1]$

        
 

题意:一个含有n个数的数组，他们的sum和是m，并且这n个数的所有子集的sum和的个数用一个数组b来表示。
其中b[i] 表示 子集中sum和为i的有b[i]个。现在给你N，M，b数组，让你推出数组a，并输出字典序最小的那一个。

思路：可以知道满足条件的只有一个数集set，所以只需要排序输出就是字典序最小的那个了。
那么如何求数组a呢？，首先我们应该知道，如果有n个0，会产生2^n个sum和为0的集合。
那么数组a中0的数量直接就是log2(b[0])了。
而sum和为1的只需要用所以的sum和为0的集合加上一个1即可，
所以num[1] = b[1]/b[0];
然后定义数组dp[i]，表示不用数字i，仅用小于i中的数凑出来sum和为i的集合数量。
那么（b[i]-dp[i]）/b[0] 就是Num[i]
求dp[i]的过程中用到dp的思想，细节见代码。

    if (dp[j] == 0) continue;
    if (num[i] == 0) break;

这步的代码可以节省时间复杂度。

code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d
",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int* p);
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int t;
int n, m;
ll b[maxn];
int dp[maxn];
int num[maxn];
int c(int n, int m)
{
    int sum = 1;
    for (int i = n - m + 1; i <= n; i++) sum *= i;
    for (int i = 1; i <= m; i++) sum /= i;
    return sum;
}
int main()
{
    //freopen("D:\common_text\code_stream\in.txt","r",stdin);
    //freopen("D:\common_text\code_stream\out.txt","w",stdout);
    // gbtb;
    // cin >> t;
    scanf("%d", &t);
    while (t--)
    {
        MS0(num);
        MS0(dp);
        scanf("%d%d", &n, &m);
        repd(i, 0, m)
        {
            scanf("%lld", &b[i]);
            // cin >> b[i];
        }
        num[0] = log2(b[0]);
        num[1] = b[1] / b[0];
        dp[0] = b[0];
        repd(i, 0, m)
        {
            for (int j = m; j >= 0; j--)
            {
                if (dp[j] == 0) continue;
                if (num[i] == 0) break;
                for (int k = 1; k <= num[i]; k++)
                {
                    if (j + k*i <= m)
                    {
                        dp[j + k*i] += dp[j] * c(num[i], k);
                    }
                }
            }
                if (i + 1 <= m)
                {
                    num[i+1]=(b[i+1]-dp[i+1])/b[0];
                }
        }
        bool flag = 0;
        for (int i = 0; i <= m; i++)
        {
            for (int j = 1; j <= num[i]; j++)
            {
                if (!flag) printf("%d", i), flag = 1;
                else printf(" %d", i);
            }
        }
        puts("");
    }



    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '
');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}