题目描述

给定一个只包含整数的序列(序列元素的绝对值大小不超过10^9),你需要计算上升子序列的个数,满足如下条件的称之为一个上升子序列:

  1. 是原序列的一个子序列
  2. 长度至少为2
  3. 所有元素都严格递增

如果两个上升子序列相同,那么只需要计算一次。例如:序列{1,2,3,3}有4个上升子序列,分别为{1,2}{1,3},{1,2,3},{2,3}

输入输出格式

输入格式:

输入的第一行是一个整数n,表示序列长度。接下来一行是n个整数,表示序列。

输出格式:

输出仅包含一行,即原序列有多少个上升子序列。由于答案可能非常大,你只需要输出答案模10^9+7的余数。

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

数据范围

对于 30% 的数据,N ≤ 5000

对于 100% 的数据,N ≤ 10^5

设dp[i]表示以a[i]为结尾的上升子序列个数的增量 因为有重复的 (都是+1的)

所以用权值树状数组维护以a[i]的这些dp值 然后每次做的时候要把上几次的减去 (去重)且这个上几次的需要累加

然后最后答案因为都多算了自己所以减去即可

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论