A 复读数组

可以通过枚举每一个数，计算有多少个区间包含。
设在这个的数组中出现的位置为。先补集转化，然后就变成了不包含的区间个数。那么的每一次相邻的出现之间的所有区间都是满足条件的。设，那么不包含的区间个数就为。

30分算法

当时，暴力计算以上式子即可。

100分做法

和都很好计算。对于，需要分为两部分，一部分为在数组中相邻的两次出现，这种情况一共被计算了次；还有一部分为在数组中的最后一次出现和下一次重复的第一次出现，这种情况一共没计算了次。分两种情况便可以计算出答案。

B 路径计数机

20分做法

枚举计算答案。

树是一条链

可以发现距离为一个定值的路径数是级别的。暴力枚举两条路径即可。

100分做法

我们先枚举和，那么满足条件的和一共有两种情况。

• 在的子树内。
• 不在的子树内。

对于第一种情况，只要不在到的路径上即可。定义为为，长度为的路径数。预处理数组即可。可以通过枚举每一条路径计算贡献得到。
对于第二种情况，只要到的路径不经过连接和的父亲的这条边即可。预处理经过每一条边，长度为的路径即可。可以通过枚举每一条路径，然后树上差分计算贡献得到。
复杂度。

C 排列计数机

10分做法

枚举所有子序列计算答案。

20分做法

设为到，选出的子序列的最大值为，当前权值为的方案数。枚举下一个数选不选，若选了且比当前最大值要大，那么权值会加一。

另一个20分做法

可以发现序列权值就是单调栈中的元素个数。那么设为第个数为单调栈里的数，总共选了个数的方案数，那么若枚举单调栈中数，那么到之间比小的数都可选可不选。

40分做法

上述的另一个20分做法可以使用前缀和优化。

m = 1

可以计算每个数出现在多少个子序列的单调栈里，即在这个数前面并比它大的数都不能选，其他数可以任选。用树状数组统计即可。

100分做法

由于是一个次多项式，是一个次多项式，那么通过逐位确定，可求出，使得（其实可以证明与斯特林数有关）。那么题目就变成了对于每一个，对于所有非空子序列的权值，求之和。
可以发现序列权值就是单调栈中的元素个数。那么求之和，可以变成枚举非空子序列，在它的单调栈中选出个元素的方案数。
那么可以使用动态规划，设为选了第个数，总共选了个数的答案。那么，即在第个数和第个数之间，所有满足的都是可能在子序列中出现。
可以先从小到大枚举，然后按照从小到大枚举，容易发现这个转移可以使用线段树优化。
复杂度。