Beauty of Sequence

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

Input

There are multiple test cases. The first line of input contains an integer

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

题意分析：

　　题目是让我们求所有子序和的总和，并且在一个子序列中相邻且相等的数不重复累加（相当于当成一个数）。

题解：

　　当你一个问题想不通的时候，可以换一个角度来思考。

　　一开始直接想统计结果，但是明显统计量是天文数字，于是觉得是不是有什么规律，也没想出来，于是就想从反面思考这个问题，既然不能直接求和，那么能不能转而去求每个点对最后的ans的贡献呢。小试了一下，发现可行。

　　另外一个问题，在一个子序列中相邻相同点只考虑一次。可以选择在这样的子序列中只计算第一个点的贡献值。也就是，考虑一个点的贡献值，只要考虑那些包含它且在它前面没有与它相等的点的所有子序列，我们可以换个角度去求这样的子序列个数，统计所有包含改节点的子序列，然后减去不符合条件的子序列（具体看代码注释）

ac代码：

1 #include
      
        2 #include
       
         3 #include
         4 using namespace std; 5 typedef long long LL; 6  7 const int maxn = 1e5 + 10; 8 const int mod = 1e9 + 7; 9 10 int a[maxn];11 int n;12 13 int bin[maxn];14 map
         
           mymap;15 16 void table() {17     bin[0] = 1;18     for (int i = 1; i < maxn; i++) bin[i] = bin[i - 1] * 2 % mod;19 }20 21 void init() {22     mymap.clear();23 }24 25 int main() {26     int tc;27     table();28     scanf("%d", &tc);29     while (tc--) {30         init();31         scanf("%d", &n);32         LL ans = 0;33         for (int i = 1; i <= n; i++) {34             scanf("%d", a + i);35             //mymap[a[i]]表示在i之前,所有以a[i]结尾的子序列的数目36             //bin[n-1]表示所有包含i的子序列，而mymap[a[i]]*bin[n-i]代表的就是不符合条件的子序列了。37             LL tmp = ((bin[n - 1] - (LL)bin[n - i] * mymap[a[i]])%mod +mod) % mod;38             ans = (ans + a[i] * tmp) % mod;39             mymap[a[i]] += bin[i - 1];40             mymap[a[i]] %= mod;41         }42         printf("%lld\n", ans);43     }44     return 0;45 }

View Code

转载于:https://www.cnblogs.com/fenice/p/5256528.html

你可能感兴趣的文章