【BZOJ4013】【HNOI2015】实验比较

做法挺显然的吧

首先我们可以把等于的直接并查集起来。那么由于保证了每个点只有一个比它小,所以我们从小的往大的连边,就变成了一棵树。

定义一个图片质量序列的长度为其中不同的值个数(也就是小于号的个数\(+1\))。

令\(f_{i,j}\)表示\(i\)的子树中的点构成长度为\(j\)的图片质量序列的方案数。

那么一个点的两个儿子间是互不干扰的,因为之间没有大小关系。

一个长度为\(i\)的序列和一个长度为\(j\)的序列合并为一个长度为\(k\)的序列的方案数为\(\binom{k}{i}\binom{i}{j-(k-i)}\)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz