链接：Luogu-P1108
这个题刚看到的时候我是懵逼的……着实被题解惊艳到了，完全想不到还有这么优美的解法。 这些解法来自各位dalao的题解，整理如下。
目录
审题
求最长下降子序列长度以及方案数。
解法1
这是我认为最复杂也最精妙的一种方法：二分单调栈。对于这种方案计数的问题，也可以做到$O(n \log n)$ 的复杂度。
修改状态
如果我们拘泥于普通 LIS 类问题的状态定义的话，显然很难以较低复杂度解决这个问题；仿照普通LIS的树状数组$O(n \log n)$做法，考虑把每个数字的 值 加入状态之中。
令 $f(i)$ 为以数字 i （注意：不是位置）结尾的最长下降子序列长度。于是显然有状态转移方程：$f(i)=\max \{f(j) \vert j>i\}+1$ 。注意这个方程中的数字 $j$ 的下标一定在 $i$ 的左边。
进行优化
我们先来考虑下如何优化利用这个方程求 LDS 的过程。暂时不考虑方案计数。
朴素的方法是在原序列中从左往右更新，对于一个位置 $i$ ，考虑它左边的所有满足 $W_j > W_i$ 的数字 $W_j$，用 $f(W_j)$ 去更新 $f(W_i)$ 。复杂度和原来的 LDS 转移方程相同。
考虑按照权值采用数据结构进行优化。
先考虑一般的权值优化：如果不考虑方案计数，我们可以把一个权值树状数组作为DP结果数组，然后就可以做到 $O(\log n)$ 的状态转移：把树状数组的+ 都换成max 就可以查前后缀最值。每次查出符合题意的最大值，再修改当前位置的数字在树状数组中的 $f(i)$（显然当前的 $f(i)$ 不会比它以前的值更差（树状数组法详见排列LCS）。这样做的总复杂度为 $O(n \log n)$。
此处要求统计方案数目，而且要求“看上去一样”的方案只算一种。而普通树状数组只能返回一个满足题意的最大值。可以修改树状数组，使得它对于某个区间最大值，可以返回所有支持的坐标，但是有些麻烦。这里介绍另一种优化的方案：单调栈。
定理1：如果应用权值单调栈来优化“取出某个序列中，下标大于某个值的元素取值的最大值”这一操作，则可以令权为单调栈的元素值，原来序列中的取值为单调栈中下标，运用二分查找进行求解。
令 $S[:f(i):]= i$，其中 $S$ 是一个从栈底到栈顶单调递减的单调栈（此时维护单调性的方式与一般的单调栈不同，见下），$sz$ 为这个单调栈的大小。由上述转移方程可知，当$S[:t+1:]$ 有值时，$S[:t:]$ 也一定已经赋值。因此这是一个栈。在这个栈中，lower_bound(k)-1 这个下标即为大于数字 $k$ 的数字对应的 $f(k)$ 的最大值。每次在$[1,sz]$ 中二分查找出lower_bound(k)-1，根据状态转移方程，更新栈中 lower_bound(k) 处的值即可。由于采用的操作是查lower_bound()，如果在修改之前栈单调，修改后栈也仍然单调，即栈始终是单调的（开始时栈为空，显然是单调的）。二分查找的复杂度为 $O(\log n)$ ，因此，这个方法的总复杂度是$O(n \log n)$。
考虑多解
考虑：如何进行多解的判断？
令当前的数字为$i$，则对应的状态是$f(i)$。
进行多解的判断，就是要能遍历处于单调栈的 $f(i)-1$ 位置对应的所有数字。于是对于单调栈的每个下标，拉一条链表，保存以该下标为长度的 LDS 的末尾数字，以及以每种数字结尾的种类数目。 拉链表后如何维护栈的单调性？在栈里面放链表中最大的数字即可。在数学课上面我们接触过恒成立问题，这里也是一样：对于原来序列中在当前遍历到的位置之后的某一个数字，如果链表中存在一个数字大于它，那么这个链表中最大的数字恒大于它。这样就保证找到的 $f(j)$ 一定是最大的，即保证不漏解。
接着来统计方案数目，如果链表非空，方案数即为以链表中各个数字结尾的方案数之和，如果链表为空，就只有一种方案。注意如果链表中某个数字小于等于当前数字，那么就应该跳过它。因为我们在栈中放到是链表中最大的数字，可以保证栈中对应位置数字大于当前数字，但是不能保证链表中每个数字都大于当前数字，和当前数字一起构成LDS。在统计方案之后，更新栈中$f(i)$的值：把统计的方案数目和此时的数字插入链表头部即可。最后进行一次去重，保证以相同数字结尾的方案，在以后只算一次。
考虑：如何实现去重？
定理2：每条从栈拉出来的链都是从头到尾单调递减的。 如果位置 $i$ 对应原序列中的值为 $W_i$，那么一定有$\forall j \in \{p|p>i 且 f(p)=f(i)\} , W_j \geq W_i$。
证明：由LDS性质可知，$j>i 且 W_j<W_i \Rightarrow f(j) \geq f(i)+1$。于是后插入某条链的数字，一定大于等于先插入链的数字，即每条拉出来的链单调。
有了单调的前提就可以做到$O(n)$直接去重，遍历链表，比较当前元素和链上下个元素，如果二者相同就去掉下一个，因为下一个元素比当前元素先插入链表，即在原序列中下个元素靠前，所以当前元素包含的方案数目不比下个元素包含的少。去重后更新栈大小，为下次二分查找做准备。
实现
令S 为单调栈，head[p] 为栈中下标p对应链表的第一个元素在原序列中的下标，cnt[i] 代表以原序列下标i处元素结尾的LDS的方案数目，con[i] 代表链表中的“下一个元素”，如上述操作即可。
注意$2^{31}=2147483648>INT_{MAX}$，需要用unsigned。
具体代码如下：
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
const unsigned MAXN = 5000, INF = 0x3f3f3f3f;
unsigned N,tot,sz,W[MAXN+10],S[MAXN+10],head[MAXN+10],cnt[MAXN+10],con[MAXN+10];
int main(){
scanf("%u",&N);
for(int i=1;i<=N;i++)
scanf("%u",&W[i]);
for(int i=1;i<=N;i++) {
unsigned pos=lower_bound(S+1,S+sz+1,W[i],greater<unsigned>())-S-1;
tot=0;
for(int j=head[pos];j;j=con[j])
if(W[j]>W[i]) //要接的位置符合单调递减
tot+=cnt[j];
if(tot==0) tot=1;
pos++;//转到当前处理的位置
con[i]=head[pos];head[pos]=i;
cnt[i]=tot;
for(int j=head[pos];j;j=con[j])
if(W[j]==W[con[j]]) cnt[con[j]]=0;
S[pos]=W[i];
sz=max(sz,pos);
}
tot=0;
for(int j=head[sz];j;j=con[j])
tot+=cnt[j];
printf("%u %u",sz,tot);
}
（代码短，思维量大…）
解法2
这是一个利用上面部分思路的 $O(n^2)$ 方法。
思路
由上可得：对于某个位置$i$，我们显然可以求得一个LDS长度$f(i)$。对于它前面的一个位置$j$，如果有$f(j)=f(i)-1$，那么对于相同的$W_j$，只累加最靠近 $i$ 的位置 $j$ 对应的方案数目。
实现
用一个set 维护是否累加过某个数值，每次求过LDS后，从后向前扫描即可。
代码：
#include <cstdio>
#include <set>
using namespace std;
const int MAXN = 5000;
unsigned N,W[MAXN+10],opt[MAXN+10],cnt[MAXN+10];
int main(){
scanf("%u",&N);
for(int i=1;i<=N;i++) scanf("%u",&W[i]);
W[++N]=0;
for(int i=1;i<=N;i++)
opt[i]=1;
for(int i=1;i<=N;i++) {
set<unsigned> vis;
for(int j=1;j<=i-1;j++)
if(W[j]>W[i])
opt[i]=max(opt[i],opt[j]+1);
for(int j=i-1;j>=1;j--)
if(W[j]>W[i] && opt[j]+1==opt[i] && vis.count(W[j])==0) {
cnt[i]+=cnt[j];vis.insert(W[j]);
}
if(!cnt[i]) cnt[i]=1;
}
printf("%u %u",opt[N]-1,cnt[N]);
}
