LISNumber

作者：叶芃

关键词：序列 计数 组合数学 动态规划

题目简述

对于一个序列，我们可以将其从左到右划分成L段递增的连续子序列。所有划分方式中最小的L称为该序列的LISNumber。

现给定1~36中每个数的出现次数(不超过36)，要将其排成一个序列，求有多少种不同的排列方案使得序列的LISNumber为$K$(若两种方案中所有位置上的数均相等则认为这两个方案相同)。($K\le 1296$)

算法一

考虑如何求一个序列$a$的LISNumber，我们从左到右扫描整个序列，如果对于某个i有$a_i>a_{i-1}$，那么我们贪心地将$a_i$接在$a_{i-1}$之后，否则我们只能让$a_i$为一个新的序列的开头。那么易知LISNumber即为满足$a_i\le a_{i-1}$的个数+1。由此我们也可知道对于一个序列的最小划分方案是唯一的。

设$f_i$表示LISNumber为$i$的方案数，$s$为序列长度，对于每个数$j$，设其出现的次数为$cnt_j$，我们每次从$i$个上升子序列中选出$cnt_j$个并将$j$加到它们末尾。事实上，这样的方案数为LISNumber$\le i$的方案数。对于每个$k < i$，由于划分方案唯一，所以LISNumber为$k$的每个方案对其的贡献为将$s$个数分成$i-k+1$段(可以为空)的方案数。因此可以得出递推式：

$f_i=\prod_{j=0}^{n-1}{i\choose cnt_j} -\sum_{k=1}^{i-1}f_k\times {s+i-k\choose i-k}$

组合数可以预处理阶乘得到。时间复杂度为$O(K^2)$

算法二

先考虑每个数仅有一个的情况，由算法一的分析可知：我们从小到大插入每个数，那么在每个时刻，序列都会被分成若干段，每段都是递增的，且每段的最后一个数都比后面一段的第一个数来得大。

令$f_{i,j}$表示添加到$i$时分成$j$段的方案数。如果当前的数加到一段的最后面，那么不影响段数，否则会导致段数+1。转移方程容易写出：

​ $f_{i,j}=f_{i-1,j}*j+f_{i-1,j-1}*(i+1-j)$

对于每个数可以存在多个的情况，转移的情况会变得复杂一些，因为会有相同的数连在一起的情况。考虑一个$f_{i,j}$，我们枚举有$k$个数会加到那些段的末尾，对于剩下的$x=cnt_{i-1}-k$个数，由于放到没有被我们选到的那$j-k$个段的末尾(否则就不会改变答案)，它们能插入的位置有$s=1+\sum_{j=0}^{i-1}cnt_j-(j-k)$个，还需要乘上将$x$个元素分成$s$段(可以为空)的方案数，于是有：

​ $f_{i,j}\times {j \choose k}\times {s+x-1\choose s-1} \rightarrow f_{i+1,j+x}$

组合数同样可以预处理，时间复杂度$O(36nK)​$