Rikka with Subset

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 139 Accepted Submission(s): 49

Problem Description

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

n positive

A1−An and their sum is

m. Then for each subset

S of

A, Yuta calculates the sum of

Now, Yuta has got

2n numbers between

[0,m]. For each

i∈[0,m], he counts the number of

is he got as

Bi.

Yuta shows Rikka the array

Bi and he wants Rikka to restore

A1−An.

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

Input

The first line contains a number

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).

The second line contains

m+1 numbers

B0−Bm(0≤Bi≤2n).

Output

For each testcase, print a single line with

n numbers

A1−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]$ 
 

Source

题意：有一个数列 a[] ,长度（n<=50）。b[i] 表示元素和为 i 的集合个数。给你一个数列 b[] ，长度（m<=10000），让你求 a[]，并按照其字典序最小输出

显然数字0的数量num[0]为log2(b[0])，数字1的数量num[1]为b[1]/b[0]

设dp[i]，表示在当前i没有的情况下，用前面已知数量的数组成数字i共有多少种情况

那么b[i]-dp[i]即为数字i与0进行组合的可能性，则num[i]=(b[i]-dp[i])/b[0]

这里如果直接写的话复杂度为o(m^2)会超时，所以需要剪枝：

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

直接将m^2的复杂度降为nm

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #define ms(a,b) memset(a,b,sizeof(a)) using namespace std;typedef long long ll;const int maxn = 1e4 + 100;ll b[maxn];int dp[maxn], 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(){ int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d%d", &n, &m); ms(dp, 0); ms(num, 0); for (int i = 0; i <= m; i++) { scanf("%lld", &b[i]); } num[0] = log2(b[0]); num[1] = b[1] / b[0]; dp[0] = b[0]; for (int i = 0; i <= m; i++) { 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;}