题解：
考虑DP
dp[i]表示前i项里面以a[i]结尾的本质不同的子序列的权值和
考虑如何不重不漏的转移
我们倒着枚举j，如果这是第一次出现a[j]，则他包括了1~j中所有以a[j]结束的本质不同的子序列；
如果不是第一次出现a[j]，那么之前已经考虑过a[j]了，这部分和前面考虑过的部分本质相同，被包含了，因此不用考虑
所以转移方程是 dp[ i ] = ( 1 + sum { dp[ j ] } )*a[ i ] (其中j是每个a[j]最后出现的位置，1是空序列加一个a[i]的情况)
然后统计答案也是倒着统计，如果a[i]没出现过那么ans+=dp[i]
优化的话树状数组弄下就好了
1 #include<bits/stdc++.h> 2 #define maxn 1000005 3 #define ll long long 4 const ll mod = 1000000007; 5 using namespace std; 6 int n,a[maxn]; 7 ll c[maxn]; 8 void add(int x,ll v) 9 { 10 for(;x<=maxn-5;x+=x&(-x))c[x]=(c[x]+v)%mod; 11 } 12 ll query(int x) 13 { 14 ll ans=0; 15 for(;x;x-=x&(-x))ans=(ans+c[x])%mod; 16 return ans; 17 } 18 ll dp[maxn]; 19 bool vis[maxn]; 20 int main() 21 { 22 scanf("%d",&n); 23 for(int i=1;i<=n;++i)scanf("%d",&a[i]); 24 for(int i=1;i<=n;++i) 25 { 26 dp[i]=a[i]+query(a[i])*a[i]; 27 add(a[i],(dp[i]-query(a[i])+query(a[i]-1)+mod)%mod); 28 } 29 ll ans=0; 30 memset(vis,0,sizeof(vis)); 31 for(int i=n;i;--i)if(!vis[a[i]])ans=(ans+dp[i])%mod,vis[a[i]]=1; 32 printf("%I64d ",ans); 33 return 0; 34 }