CF403D Beautiful Pairs of Numbers

Beautiful Pairs of Numbers"/>

CF403D Beautiful Pairs of Numbers

题意：
在一个长度为n的序列中，找k个长度互不相同的区间互不重叠，求方案数。
其实每个区间长度不等是个很烦的限制。
不如按照从小到大排序，最后再打乱即可。
发现还可以保证所有区间相邻，即前一个区间的右边界，就是下一个区间的左边界-1，这样把剩下的空格填充进去即可。
问题转化为：
区间总长度为 i i i，里面放入 j j j个相邻的区间，前面比后面小，有多少种方法。
感觉这个dp挺妙的。
f i + j , j + = f i , j f i + j + 1 , j + 1 + = f i , j f_{i+j,j}+=f_{i,j}\\f_{i+j+1,j+1}+=f_{i,j} fi+j,j​+=fi,j​fi+j+1,j+1​+=fi,j​
表示所有区间一起增加1或者一起增加1后在前面加入一个大小为1的区间（由于可能最小的区间大小为1，所以要先加。可以证明一定能包含所有情况）。
然后从k到n枚举总区间长度，假设为n’。
把一个区间看成一个球，加上后面的剩下n-n’的空位，一共有n-n’+k个球，随意排列
所以答案加上 f n ′ , k × ( n − n ′ + k k ) × k ! f_{n',k} \times \binom{n-n'+k}{k} \times k! fn′,k​×(kn−n′+k​)×k!即可。