Sequence [组合数学]
时间限制: 3 Sec 内存限制: 128 MB 提交: 138 解决: 52 [提交][状态][讨论版]
题目描述
在某个夜黑月高的晚上，！！！，原谅我编不下去了。
HS(Handsome)的Ocean在纸上写下$N$个整数，Ocean把它定义为$O$序列。
Ocean认为一个序列的价值的是：序列中不同元素个数。
现在他想知道$O$序列中所有子序列的价值之和。
比如说：序列$(1, 1, 2, 2)$价值为$2$，因为序列中有$1$和$2$两个不同元素。 比如序列$(1, 1, 1)$，共有$7$个子序列，$(1)、(1)、(1)、(1, 1)、(1, 1)、(1, 1)、(1, 1, 1)。$价值之和为$7$。
输入
第一行输入一个整数$T$，代表有$T$组测试数据。 每组数据占两行，第一行输入一个整数$N$，代表序列元素个数。 接下来一行输入$N$个整数$a_i$。
注：$1 <= T <= 10000，1 <= N <= 50，1 <= a_i <= 10。$
注：$1 <= T <= 10000，1 <= N <= 50，1 <= a_i <= 10。$
输出
对每组测试数据，输出一个结果代表所有子序列价值之和。由于结果会很大，请用$long\,long$(%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
来源
思路：每个元素提供的价值是2^k - 1,k是这个元素出现的次数；那么我们根据元素值来解决问题，假设我们选的是5和7，
现在有一组 5 5 5 7 7 7 7，那么选的这两个数提供的价值就是V5 * V7；
那么我们现在只需要找出元素值的全排列的选择即可，这个可以用位运算；
代码：（注意java里面跟c有点不一样，要想是java形式，要是1L<<k）
import java.util.Scanner;
public class hpu1192 {
static private Scanner cin;
static{
cin = new Scanner(System.in);
}
public static void main(String[] args) {
// System.out.println((long)(1L << 50));
int T, N, temp;
int[] a = new int[11];
T = cin.nextInt();
while(T-- > 0){
N = cin.nextInt();
for(int i = 0; i <= 10; i++){
a[i] = 0;
}
for(int i = 0; i < N; i++){
temp = cin.nextInt();
a[temp]++;
}
long ans = 0;
for(int i = 1; i < (1 << 10); i++){
int cnt = 0;
long sum = 1;
for(int j = 0; j < 10; j++){
if((i & (1 << j)) != 0){
cnt++;
sum *= (long)((1L << a[j + 1]) - 1);
}
}
ans += (long)sum * cnt;
}
System.out.println(ans);
}
}
}