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 of
integers
. You need find the summation of the beauty of all the sub-sequence of
. As the answer may be very large, print it modulo
.
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 is a sub-sequence of
.
Input
There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:
The first line contains an integer
, indicating the size of the sequence. The following line contains
integers
, denoting the sequence
.
The sum of values for all the test cases does not exceed
.
Output
For each test case, print the answer modulo
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
找到递推方法然后就好了。。。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn = 300005;
const LL base = 1e9 + 7;
int T, n, m, a[maxn], b[maxn], c[maxn];
LL now, bef, f[maxn], sum[maxn], tot;
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n); tot = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
sum[i] = f[i] = 0;
}
sort(b + 1, b + n + 1);
m = unique(b + 1, b + n + 1) - b;
now = 1;
for (int i = 1; i <= n; i++) c[i] = lower_bound(b + 1, b + m, a[i]) - b;
for (int i = 1; i <= n; i++)
{
bef = (now - f[c[i]] + base) % base*a[i] % base;
(f[c[i]] += now) %= base;
(sum[c[i]] += tot + bef) %= base;
((tot <<= 1) += bef) %= base;
(now <<= 1) %= base;
}
printf("%I64d\n", tot);
}
return 0;
}