题解 AT2649 [ARC077B] 11

算是排列组合基础题。

首先题目有个隐藏条件,即只有一个重复的数。

首先很明显,假设我们不考虑重复的话,答案为:
\(C_{k}^{n+1}\)

那么我们只需算出重复的,两者相减即可。

那么我们记录一下这个重复的数字第一次和最后一次出现的位置,设为 \(l,r\)

那么,显然在 \(l,r\) 之间的都是无解的,即重复的。

那么问题就变成了,在 \([1,l-1]\)\([id+1,r]\) 中选出 \(k-1\) 个数。

这个直接套组合数,就是 \(C_{k-1}^{l-1+n+1-id-1}\)

所以答案就是\(C_{k}^{n+1}-C_{k-1}^{l-1+n+1-id-1}\)

转载请注明出处:http://www.fuqingkongyaji.com/article/20230526/839643.html