点击打开链接
1192: Sequence [组合数学]
时间限制: 3 Sec 内存限制: 128 MB提交: 150 解决: 57 统计
题目描述
在某个夜黑月高的晚上，！！！，原谅我编不下去了。
很美吧？放松之后，继续做题吧。
HS(Handsome)的Ocean在纸上写下NN个整数，Ocean把它定义为OO序列。
Ocean认为一个序列的价值的是：序列中不同元素个数。
现在他想知道OO序列中所有子序列的价值之和。
比如序列(1,1,1)(1,1,1)，共有77个子序列，(1)、(1)、(1)、(1,1)、(1,1)、(1,1)、(1,1,1)。(1)、(1)、(1)、(1,1)、(1,1)、(1,1)、(1,1,1)。 价值之和为77。
输入
第一行输入一个整数TT，代表有TT组测试数据。
每组数据占两行，第一行输入一个整数NN，代表序列元素个数。
接下来一行输入NN个整数aiai。
注：1<=T<=10000，1<=N<=50，1<=ai<=10。1<=T<=10000，1<=N<=50，1<=ai<=10。
每组数据占两行，第一行输入一个整数NN，代表序列元素个数。
接下来一行输入NN个整数aiai。
注：1<=T<=10000，1<=N<=50，1<=ai<=10。1<=T<=10000，1<=N<=50，1<=ai<=10。
输出
对每组测试数据，输出一个结果代表所有子序列价值之和。由于结果会很大，请用longlonglonglong(%lld)。
样例输入
4
3
1 1 1
4
1 1 1 1
4
10 10 10 8
20
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
样例输出
7
15
22
7864320 题解：这题就是递推
下面是代码：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int num[50];
long long a[50];
int main()
{int T;scanf("%d",&T); while(T--){memset(num,0,sizeof(num));memset(a,0,sizeof(a));long long n,b,s=0,ans=0,endd;scanf("%lld",&n);for(int i = 0 ; i < n ; i++){scanf("%lld",&b);num[b]++;}for(int i= 1 ; i <=10 ; i++){s++;if(num[i]!=0){endd=pow(2,num[i])-1;for(int j = s ; j >= 1 ; j--){if(j==1)a[j]+=endd;elsea[j]+=a[j-1]*endd;}}}for(int i = 1 ; i <= s ; i++){if(a[i])ans+=a[i]*i; }printf("%lld\n",ans); }return 0;
}