赛时状态极差,打醉拳想出来的奇怪概率做法。
首先前 \([1,n-k]\) 的位置是等效的。先刻画 \(b\) 的限制,发现 \(a\) 中前 \(n-k\) 个位置中被操作过的位置一定比没操作过的位置大,且其它位置一定是单调递增,于是在 \(b\) 中其它位置形成的子序列必然是一个有序的排列,即 \([1,2,3,\cdots]\)。
而 \(b\) 的作用就是限定了被操作位置数的范围,显然我们并不需要关系被操作的是哪些位置,只需要关心数量即可。并且我们已经确定了这些位置的唯一顺序,所以我们计数时将后面的值视为无序,只需要关心有多少种方案使得操作设计设计到了 \(l\) 个位置即可。
注意到对于 \(\forall i\in[1,n-k],j\in[n-k+1,n]\),满足 \(P(a_i=j)=\frac 1 n\)。
证明可以考虑归纳。归纳时我们保持 \(n\) 不变是好的,现在考虑往前面加一个数,也就是 \(k\leftarrow k+1\),对于当前 \(n-k+1\) 的数,前面 \(a_i=n-k+1\) 的概率是 \(\frac {n-k+1}{n}\times \frac 1 {n-k+1}=\frac 1 n\)。对于后面的数有两种情况,一种是提前被选且 \(n-k+1\) 没覆盖,概率为 \(\frac 1 n\times\frac {n-k}{n-k+1}\),另一种是 \(n-k+1\) 已经提前被要的值选了,概率为 \(\frac 1 n\times\frac {1}{n-k+1}\),加起来恰为 \(\frac 1 n\)。
考虑对涉及到 \(l\) 个位置计数。我们不妨利用条件概率,先把操作框在前 \(l\) 个位置和后 \(k\) 个位置之间,概率为 \(\prod_{i=1}^k \frac{l+k-i+1}{n-i+1}=\frac{(l+k)!(n-k)!}{l!n!}\)。然后在这些数之间,我们先选出 \(\binom{k}{l}\) 个数出来,然后对于一种方案的概率有 \(\frac{k!}{(l+k)!}\),感性理解一下,确定了一个数的值后,确定下一个值的难度与删去一个位置是等效的。严谨证明可能比较屎,我有一个证明,这里太小了写不下。如果有简洁证明的巨佬可以教教我~