我们目前的碰到几乎所有大厂笔试,所使用的都是IOI赛制。通俗来讲,该赛制允许进行无数次提交,按最高分计算。每次提交后台有n组测试样例(一组样例由一个输入数据和一个输出数据组成),我们所得的分数为n正确的组数∗100%。也就是说我们允许使用非标准解法拿部分分
一种最常见的技巧是:碰到想不出满分最优解的题目,我们可以迅速的用暴力写完拿完部分分(部分情况下可达70%),把时间留给我们会的题目。我们本道题目是来自24年字节跳动9.25机考最后一道题目,是一道较困难的,数据结构优化的动态规划题目。
小塔有一个长度为n的数组a1,a2,...,an,请你帮助他求出有多少个严格单调递减的子序列。结果可能很大,对109+7取模后在输出。
严格单调递减序列是指一个序列满足:长度为1或从第2项开始,每一项均小于前一项的序列。
由原来的序列删除(或不删除)某些元素而不改变其余元素的相对顺序的序列称为子序列。
第一行输入一个整数 n(1≤n≤2×105)代表数组中的元素数量。
第二行输入n个整数a1,a2,...,an(1≤ai≤109)代表元素。
在一行输出一个整数,代表严格单调递减的子序列的个数,由于数据较大,输出答案对109+7取模的结果。
输入
4
1 3 5 2
输出
6
说明
由两个元素构成的满足题意的子序列为{3,2}、{5,2}