自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 22:39:00，当前版本为作者最后更新于2022-06-18 00:53:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这里仅介绍 $100\%$ 的方法。

考虑我们把一个有序的定长度序列 $a_i$ 转换为每个数出现的次数 $c_i$。那么我们就只用考虑第二个限制了。

考虑到 $k$ 的奇偶性对公式有影响，故分开讨论。

当 $\bm k$ 为偶数时，$\bm {k=2m}$.

那么 $c_i,c_{k+1-i}$ 至少有一个为 $0$。实际上，我们可以把这一些 $c_i,c_{k+1-i}$ 分为一组，一共 $m$ 组。

枚举 $m$ 组当中有不为零的组数 $i$。可以发现这样子有 $C_m^i\times C_{n-1}^{i-1}\times 2^i$。这里的三项分别表示

• 选择 $i$ 组的方案。
• 把 $n$ 个元素分配到这 $i$ 组的方案。
• 这 $m$ 组内部分配的方案。

所以答案就是

$$\sum_{i=1}^{\min(n,m)}C_m^i\times C_{n-1}^{i-1}\times 2^i $$

当 $\bm k$ 为奇数时，$\bm {k=2m+1}$.

同偶数的情况，唯一不同的就是要特殊讨论 $c_{m+1}$ 处，至多为 $1$。从 $c_{m+1}=0/1$ 的角度出发同上处理可得答案。

$$\sum_{i=1}^{\min(n,m)}C_m^i\times C_{n-1}^{i-1}\times 2^i+\sum_{i=1}^{\min(n-1,m)}C_m^i\times C_{n-2}^{i-1}\times 2^i $$

---

upd (2022.7.10) 记得特判 $n/k=1$ 的情况。