hdu5496 Beauty of Sequence-白红宇

hdu5496 Beauty of Sequence

阅读量：5056 次

发布时间：2019-06-12

本文共 2630 字，大约阅读时间需要 8 分钟。

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 383 Accepted Submission(s): 167

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}.

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

(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

这题看了好长时间题解，终于理解了。因为子序列太多，所以可以考虑每一个元素贡献的价值，对于每个数, 我们只算它出现在连续相同元素的第一个时的贡献, 这样会使计算简便很多. 假设当前的数是a[i], 那么i后面的数可以随便选有2^(n-i)种. 考虑a[i]前面的数, 要么一个不选, 要么选择的最后一个数和a[i]不同, 那么我们只要把前面出现过的i的位置记录下来，分别为b,c,d,..那么总的个数为2^(i-1)-2^(b-1)-2^(c-1)-...这样就可以算出来了。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define ll long long#define inf 0x7fffffff#define maxn 100070#define MOD 1000000007map
                  
                   mp;map
                   
                    ::iterator it;ll a[maxn],cishu[maxn];ll kuaisumi(ll a,ll b,int c){ ll ans = 1; a=a%c; while(b>0) { if(b%2==1) ans=(ans*a)%c; b=b/2; a=(a*a)%c; } return ans;}ll mul(ll x){ return kuaisumi(2,x,MOD);}int main(){ ll m,i,j,T; ll n; scanf("%lld",&T); while(T--) { scanf("%lld",&n); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); } memset(cishu,0,sizeof(cishu)); mp.clear(); ll ans=0; for(i=1;i<=n;i++){ if(!mp.count(a[i])){ ans=(ans+a[i]*mul(n-1))%MOD; } else{ ans=(ans+ a[i]*( mul(i-1)-mp[a[i] ])%MOD*mul(n-i)%MOD )%MOD; } mp[a[i] ]=(mp[a[i] ]+mul(i-1) )%MOD; } printf("%lld\n",(ans+MOD)%MOD); } return 0;}

转载于:https://www.cnblogs.com/herumw/p/9464645.html

你可能感兴趣的文章

程序员必备英语.net版（.net菜鸟的成长之路-零基础到精通）