题解：P14686 [ICPC 2025 Yokohama R] Charity Raffle

· · 题解

考虑刻画一下，什么样的序列是可以被造出来的？

如果最大值等于次大值，一定可以。如果最大值等于次大值 +1，必须在最大值后面存在一个次大值。其他序列都不可以被构成。考虑先把最大值次大值造出来，一样的话两个一起叠叠叠，最大值等于次大值 +1 的话最后一步要选编号小的，所以必须最大值后面存在一个次大值。

这个刻画已经很简洁了，但是他仍然要分类。我们考虑换一个方式？既然正着数是两个条件叠一起，倒过来，不合法的就是，设最大值为 x 在 p，那么 [1,p) 满足 \leq x-1，(p,n] 满足 \leq x-2，这样的序列就是不合法的。

其实做到这一步，瞎容斥一下推推式子还是可以的。但是有个更深刻的双射观察：

我们发现不合法序列都可以这样被生成出来：生成一个序列，最大值为 x，在最后一个 x 出现的位置 p，把 p 上的数变成 x+1。

那么不合法序列和『长度为 n 总和为 k-1 且每个元素不超过 m-1 的自然数序列』形成双射。

拿总数『长度为 n 总和为 k 且每个元素不超过 m 的自然数序列』减去上面这个即可。

至于这个怎么算，直接容斥，\geq m+1 的元素都减去 m+1，钦定若干个元素减去了 m+1 然后任意。就是 \sum\limits_{i=0}^{\min\{\lfloor\frac{k}{m+1}\rfloor,n\}}\binom{n}{i}\times (-1)^i\times \binom{k-i\times (m+1)+n-1}{n-1}。

注意因为插板法组合数有个 +n-1，所以处理组合数要处理到两倍即 2\times 10^6 的范围。