求助,关于容斥的一个错误做法证伪
查看原帖
求助,关于容斥的一个错误做法证伪
692274
hgckythgcfhk楼主2024/1/27 14:36

设 f(i)f(i) 为 至少 ii 个元素相等的集合,则 f(i+1)f(i+1) 一定是 f(i)f(i) 的子集,所以恰好 ii 个相等的个数是 ∣f(i)∣−∣f(i+1)∣|f(i)|-|f(i+1)|,看起来非常合理,但为什么不对?对于本题的特殊情况,我认为 ∀x>=i+1\forall x>=i+1 一定满足 x>=ix>=i,即 ∀x∈f(i+1),x∈f(i)\forall x \in f(i+1),x\in f(i) 所以 f(i)f(i) 可以看作为答案集合的后缀和,直接差分是正确的,但是事实上,这样做只会得 3737 pts,不考虑由于哈希冲突带来的小概率错误,即使是用可以做到一定不冲突的 __int128 和 vector 等哈希方法也不对,各种哈希方法都试过,在以下构造的随机数据中,题解输出均为 2424 而我的做法输出 2828,求一个形式化的证伪。

2024/1/27 14:36
加载中...