Beauty of Sequence
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 384 Accepted Submission(s): 168
Problem Description
Sequence is beautiful and the beauty of an integer sequence is defined as follows: removes all but the first element from every consecutive group of equivalent elements of the sequence (i.e. unique function in C++ STL) and the summation of rest integers is the beauty of the sequence.
Now you are given a sequence A of n integers {a1,a2,...,an}. You need find the summation of the beauty of all the sub-sequence of A. As the answer may be very large, print it modulo 109+7.
Note: In mathematics, a sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example {1,3,2} is a sub-sequence of {1,4,3,5,2,1}.
Now you are given a sequence A of n integers {a1,a2,...,an}. You need find the summation of the beauty of all the sub-sequence of A. As the answer may be very large, print it modulo 109+7.
Note: In mathematics, a sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example {1,3,2} is a sub-sequence of {1,4,3,5,2,1}.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1≤n≤105), indicating the size of the sequence. The following line contains n integers a1,a2,...,an, denoting the sequence(1≤ai≤109).
The sum of values n for all the test cases does not exceed 2000000.
The first line contains an integer n (1≤n≤105), indicating the size of the sequence. The following line contains n integers a1,a2,...,an, denoting the sequence(1≤ai≤109).
The sum of values n for all the test cases does not exceed 2000000.
Output
For each test case, print the answer modulo 109+7 in a single line.
Sample Input
3
5
1 2 3 4 5
4
1 2 1 3
5
3 3 2 1 2
Sample Output
240
54
144
Source
题目大意：定义了beauty，给出一个整数序列, 去除序列中连续相邻的重复元素(只保留一个), 剩下来的数的和称之为序列的beauty.给你一个序列，问你该序列的所有子序列的beauty和对1e9+7的结果。
解题思路：
我们枚举1---n的每个数字a[i]，对于a[i]来说，能产生多少次贡献呢？。i后边的所有组合以及i前边的不是以a[i]为结尾的所有组合的乘积。现在问题转为如何维护不是以a[i]为结尾的所有组合的个数。我们定义事件A：以a[i]为结尾的组合的个数，事件B：不是以a[i]为结尾的组合的个数。 那么 B=2^（i-1)-A。我们现在可以维护A，也就间接维护了B。笔者是用map维护的，其实都无所谓的。如序列：2 1 3 1 1 1。下标从1开始。如i=5时，如果前边有a[i-1]的话，那么就不是i位置产生的贡献，而是i-1位置产生的贡献。但是i-1位置在计算该位置产生贡献的时候已经计算过了，所以不应该重复计算，其他以数字a[i]结尾的位置同理。所以应该找到前边跟a[i]不同的数结尾的组合。
#include<bits/stdc++.h>
using namespace std;
typedef long long INT;
const int mod=1e9+7;
const int maxn=1e5+200;
INT a[maxn];
INT pow2[maxn];
map<int,INT>coun;
int main(){
int T,n;
scanf("%d",&T);
pow2[0]=1;
for(int i=1;i<=maxn-100;i++){
pow2[i]=pow2[i-1]*2%mod;
}
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
}
coun.clear();
coun[0]=1;
INT ans=0;
for(int i=1;i<=n;i++){
INT pre=coun[a[i]];
INT tpre=pow2[i-1]-pre; //i-1
tpre=(tpre%mod+mod)%mod;
INT tmp=a[i]*tpre%mod*pow2[n-i]%mod;
ans=(ans+tmp)%mod;
pre=pow2[i-1]+pre;
coun[a[i]]=pre;
}
printf("%I64d
",ans);
}
return 0;
}