这道统计LIS方案数的是真的烦啊。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=5e3+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
} 
int f[N],s[N],a[N];bool v[65537];
int main()
{
    int n;qr(n);
    for(int i=1;i<=n;i++)qr(a[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;s[i]=1;memset(v,1,sizeof(v));
        for(int j=i-1;j;j--)
            if(a[i]<a[j])
            {
                /*
                    对于j<k<i,a[j]==a[k]而言,f[j]==f[k],s[j]==s[k]的情况一定成立,当且仅当,对于所有的w,j<w<k,a[w]<a[j]时成立。
                    否则f[j]<=f[k],s[j]<=f[k]。 
                    若为上式,f[k]能利用的也仅仅只是f[j]能利用的,因此它们的决策集合相同,因此方案数相等,且每一个方案一一对应。
                    这就是要去重的地方,用一个bool数组记录a[j]有没有出现过就好了。
                    倒序处理是因为后面的状态会更优(不论在上述讨论的哪一种情况,即哪一种都符合),
                    否则就需要memset了。 
                    也正是因为如果后面状态更优,若有i<k,f[i]<f[k],a[i]==a[k],
                    如果正序处理的话,a[i]被提前标记,这是违背了初衷的。
                    同时也可以说明若a[i]==a[k],i<k,k的决策集合是i的决策集合的母集。 
                */
                if(f[i]<f[j]+1)
                {
                    f[i]=f[j]+1;
                    s[i]=s[j];
                    v[a[j]]=0;
                }
                else if(f[i]==f[j]+1)
                {
                    s[i]+=s[j]*v[a[j]];
                    v[a[j]]=0;
                }
            }
    }
    int ans=0,anss=0;
    memset(v,1,sizeof(v));
    for(int i=n;i;i--)
    {
        if(ans<f[i])ans=f[i],anss=s[i],v[a[i]]=0;
        else if(ans==f[i])anss+=s[i]*v[a[i]],v[a[i]]=0;
    }
    qw(ans),putchar(' '),qw(anss);puts("");
    return 0;
}