hpuoj-1010-QAQ的序列价值【状压】【数学组合】

题目链接：点击打开链接

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; }