Let Me Tell You a Story

Chasing_Meteors · 2025-11-28 15:39:13 · 题解

题目所求为一个集合

其中 A 是一个下标序列，满足：A_i\le n，且 A_i\ne A_j。且 \overline A 所对应的序列单调不升。且 A 删除最后一个数得到的序列 B 的补集 \overline B 所对应的序列不是单调不降的。

问 |S|。

我们记 f(k) 表示 |A|=k 的序列 A 的数量，g(k) 表示不需要满足 \overline B 对应序列不是单调不降的 A 的数量。

不难发现，f(k)=g(k)-(n-k+1)g(k-1)。

我们所求就是 \sum f(k)。

不妨带入 g(k)，则所求为

去枚举 A 不好做，不妨枚举 \overline A 所对应的序列 P。

我们发现，所有 \overline P 的所有排列之和恰好是 g(n-|P|)。

我们记 h(k) 表示长度为 k 的 P 的数量。

则 g(k)=h(n-k)\times k!。