转载注明来源:https://www.cnblogs.com/syc233/p/13693730.html


先不考虑序列长度至少为 \(2\) 的限制和去重,那么这道题就是一个简单的DP:

\(f_i\) 表示以 \(a_i\) 结尾的上升子序列个数,那么很容易写出转移方程:

\[f_i=\sum_{j=1}^{i-1}f_j[a_j<a_i] \]

直接转移 \(O(n^2)\) ,可以用树状数组优化到 \(O(n \ {\rm{\log}} \ n)\)

考虑如何去重。发现若对于当前数 \(a_i\) ,存在 \(a_j=a_i,1\leq j<i\) ,那么 \(a_i\) 对上升子序列的贡献会与 \(a_j\) 的贡献重复。

显然,能转移到 \(j\) 的状态一定能转移到 \(i\) ,能转移到 \(i\) 的状态不一定能转移到 \(j\) ,即重合部分就是 \(f_j\)

转移时,对于值域中的每一个数 \(x\),记录上一次计算出的 \(f_i,a_i=x\) 。转移时将重复部分减去即可。

因为题目要求序列长度至少为 \(2\) ,最后再减去长度为 \(1\) 的情况。


\(\text{Code}:\)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 100005
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
const lxl mod=1e9+7;

template <typename T>
inline void read(T &x)
{
	x=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	x*=f;
}

int n,a[maxn],b[maxn],m;

lxl sum[maxn],las[maxn];

inline int lowbit(int x) {return x&-x;}

inline void add(int x,lxl d)
{
	for(int i=x;i<=m;i+=lowbit(i))
		(sum[i]+=d)%=mod;
}

inline lxl query(int x)
{
	lxl res=0;
	for(int i=x;i>=1;i-=lowbit(i))
		(res+=sum[i])%=mod;
	return res;
}

int main()
{
	// freopen("P3970.in","r",stdin);
	read(n);
	for(int i=1;i<=n;++i)
	{
		read(a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i)
	{
		a[i]=lower_bound(b+1,b+m+1,a[i])-b;
		lxl val=query(a[i]-1)+1-las[a[i]];
		add(a[i],val);
		las[a[i]]+=val;
	}
	printf("%lld\n",query(m)-m);
	return 0;
}