P3970 [TJOI2014]上升子序列

    • 204通过
    • 895提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 排序 树状数组 概率论,统计 线段树 各省省选 2014 天津
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个只包含整数的序列(序列元素的绝对值大小不超过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: 复制
    4
    1 2 3 3
    输出样例#1: 复制
    4

    说明

    数据范围

    对于 30% 的数据,N ≤ 5000

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。