关于 S T3 Hash 做法正确率
  • 板块学术版
  • 楼主Zxc200611
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/10/30 08:44
  • 上次更新2023/10/27 04:58:05
查看原帖
关于 S T3 Hash 做法正确率
175586
Zxc200611楼主2022/10/30 08:44

这里的 Hash 做法是指每个点随机一个权值,将所有点的出度 outout 与权值 valval 相乘并求和,判断是否为 val\sum val,即判断:

i=1nouti×vali=i=1nvali\sum_{i=1}^n out_i \times val_i = \sum_{i=1}^n val_i

非常粗略地算了一下,如果有一些 valval 加起来是 00 就可能挂,或者一些 valval 的和与另一些 valval 的和相等就可能挂。

这样相当于 2105+31052^{10^5}+3^{10^5} 个数中有一个是 00 就会挂?

这样的正确率貌似不太高?

2022/10/30 08:44
加载中...