本题题解有误
查看原帖
本题题解有误
356003
Moeebius楼主2024/10/16 18:52

https://www.luogu.com.cn/article/9ykow1tj 这篇题解中有如下结论:

非严格递增的 [li,ri][l_i,r_i] 区间长度总和不超过 2222

这个结论本身正确,但是作者对其的证明似乎并不正确(也可能是作者没表述清楚,或者严重跳步了)

对于每一个位置 i<ni<n[1,i][1,i](i,n](i,n] 之间一定存在一个逆序对并不能推出序列总逆序对个数不少于 n1n-1,因为同一个逆序对可能被计入多次。


此外,文末组合数 (nij)\binom{n-i}{j} 疑似为作者笔误,应为 (ni+jj)\binom{n-i+j}{j}

2024/10/16 18:52
加载中...