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了＝￣ω￣＝

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,arr[5005],f[5005],cnt[5005],ans1,ans2;
set<int> book;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&arr[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=cnt[i]=1,book.clear();
        for(int j=i-1;j>0;j--)
            if(arr[i]<arr[j])
            {
                if(f[i]<f[j]+1)f[i]=f[j]+1,book.insert(arr[j]),cnt[i]=cnt[j];
                else if(f[i]==f[j]+1&&!book.count(arr[j]))
                    cnt[i]+=cnt[j],book.insert(arr[j]);
            }
    }
    book.clear();
    for(int i=n;i>=1;i--)
        if(f[i]>ans1)book.insert(arr[i]),ans1=f[i],ans2=cnt[i];
        else if(f[i]==ans1&&!book.count(arr[i]))
            ans2+=cnt[i],book.insert(arr[i]);
    printf("%lld %lld\n",ans1,ans2);
    return 0;
}