51nod1202【DP-树状数组维护】

思路： DP[i]代表从1 到 i 以 a[i] 为末尾的子序列个数，dp[i]=dp[i]+dp[j](a[i]!=a[j]) +1

利用树状数组维护以值 a[i] 结尾的子序列个数。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL mod=1e9+7; const int N=1e5+10; LL c[N]; int lowbit(int x) { return x&(-x); } void add(int d,LL v) { while(d<N) { c[d]=(c[d]+v)%mod; d+=lowbit(d); } } LL Sum(int x) { LL ans=0; while(x) { ans=(ans+c[x])%mod; x-=lowbit(x); } return ans; } int main() { int n,x; memset(c,0,sizeof(c)); scanf("%d",&n); for(int i=1;i<=n;i++) { LL sum=0; scanf("%d",&x); sum=(Sum(100000)+1)%mod; sum=(sum-Sum(x)+Sum(x-1)+mod)%mod; add(x,sum); } printf("%lld\n",Sum(100000)); return 0; }