ぽかぽかの星 题解
Otomachi_Una_
·
·
题解
这里仅介绍 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 的情况。