hpuoj-1010-QAQ的序列價值【狀壓】【數學組合】

題目連結：​​點選打開連結​​

[數學、狀态壓縮]

時間限制: 3 Sec  

記憶體限制: 128 MB

送出: 73  

解決: 20

[

​​送出​​][

​​狀态​​][

​​讨論版​​]

題目描述

QAQ有一個序列，元素個數有N

N個。

他認為一個序列的價值的是：該序列中不同元素之和。

比如說：序列(1,1,2,2)

(1,1,2,2)價值為3

3。

現在QAQ想知道所有子序列的價值之和。

輸入

第一行輸入一個整數T

T，代表有T

T組測試資料。

每組資料占兩行，第一行輸入一個整數N

N，代表序列元素個數。

接下來一行輸入N

N個整數a[]

a[]。

注：1<=T<=10000，1<=N<=50，1<=a[]<=10

1<=T<=10000，1<=N<=50，1<=a[]<=10。

輸出

對每組測試資料，輸出一個整數代表所有子序列價值之和。

結果很大，請對(109+7)

(109+7)取餘。

樣例輸入

2
3
1 1 1
4
10 10 10 8      

樣例輸出

7
204      

提示

對于第二組測試資料一共有15

15個子序列：

（10）、（10）、（10）、（8）、（10,10）、（10,10）、（10,10）、
    （10）、（10）、（10）、（8）、（10,10）、（10,10）、（10,10）、
（10,8）、（10,8）、（10,8）、（10,10,8）、（10,10,8）、
    （10,8）、（10,8）、（10,8）、（10,10,8）、（10,10,8）、
（10,10,8）、（10,10,10）、（10,10,10,8）
    （10,10,8）、（10,10,10）、（10,10,10,8）。價值之和為204
    204。      

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const LL MOD=1e9+7;
int n;
int mark[11];
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n);
    memset(mark,0,sizeof(mark));
    for(int i=1;i<=n;i++)
    {
      int x;
      scanf("%d",&x);
      mark[x]++;
    }
    LL ans=0;
    for(int i=1;i<1<<10;i++)
    {
      LL sum=0,cnt=1;
      for(int j=0;j<10;j++)
      {
        if(i&(1<<j))
        {
          sum+=(j+1);
          cnt=cnt*(((1LL<<mark[j+1])-1)%MOD)%MOD; // 序列的價值 = 每個子序列的貢獻相乘 
        }
      }
      ans=(ans+sum*cnt%MOD)%MOD;
    }
    printf("%lld\n",ans);
  }
  return 0;
}