1. 题目

传送门= ̄ω ̄=

2. 题解

一开始看错题以为是统计条数不用判重。。。
统计最长下降子序列条数且不能有重复序列。。。
最先想到hash一下。。。
可是显然,$2^{31}$次方连int都存不下。。。你一个个数出来还不gg。。。

设$f(i)$为以第$i$个数字结尾的最长下降子序列长度,$cnt(i)$为以第$i$个数字结尾的最长下降子序列的条数(不重复),$arr[i]$为第$i$个位置上的数字。

不难发现对于第$i$个数字,状态从第$j$个数字转移过来,如果能让$f(i)$更新那么就直接让$cnt(i)=cnt(j)$。否则:如果$f(i)==f(j)+1$则判断是否已经用数字$arr[j]$更新过$f(i)$了,如果没有则让$cnt(i)+=cnt(j)$。

这样搞个set哈希一下就可以了。
但是会TLE啊!因为要不停地更新$f(i)$,不停地清空set。

仔细想想,可以看出如果有两个相同的数字,一个在位置$x$,一个在位置$y$,且$x<y<i$,那么如果能用$f(x)$更新$f(i)$,就一定能用$f(y)$更新$f(i)$。换而言之,如果不能用$f(y)$更新$f(i)$,就一定不能用$f(x)$更新$f(i)$。

所以找最长下降子序列时枚举$j$时从大到小枚举就行了,就不用更新$f(i)$时清空set了。

于是就AC了= ̄ω ̄=

代码: