有关 bitset

学术版

Melo_qwq @ 2025-08-02 13:02:21

lz 已知 bitset 的 count 是 N/w 的，N 是总位数。

那么今天我写了一份 \Theta(\frac{n^3}{w}) 的代码，n\le3000，时限 1s。

结果我发现跑的飞快，甚至薄纱一些正解，所以来问问是怎么回事。

数据强度可以保证，bitset 这么牛吗。

by Melo_qwq @ 2025-08-02 13:05:05

不一定跑满，但是我的意思是这 bitset 也太快了，不算 bitset 剩下的部分就是暴力

by _Chronostatis_ @ 2025-08-02 13:10:04

@Melo_qwq 注意到，3000^3 和 (10^5)^2 差不了多少，而 (10^5)^2 可以用 bitset 卡常

by Melo_qwq @ 2025-08-02 13:16:02

@Chronostatis不是哥们，你差了将近 3 倍的常数啊

而且你的 1e10 也不一定能用 bitset 卡常，只是有时候可以

所以您的回答对我没有帮助

by Melo_qwq @ 2025-08-02 13:16:43

@liyelei我没问 bitset 和 bool 的区别，能看清我的问题再回答吗。。。

by Dont_Be_Afraid @ 2025-08-02 13:21:39

@Melo_qwq sorry，紫衫了

by Melo_qwq @ 2025-08-02 13:36:07

@fkxr肯定不是啊

by fkxr @ 2025-08-02 13:37:10

我奶龙，别管

by 快速数论变换 @ 2025-08-02 13:45:54

@Melo_qwq 你可以手算一下 3000^3\div64 等于多少

by _Chronostatis_ @ 2025-08-02 13:46:48

@Melo_qwq 一般计算的复杂度都是最坏复杂度，大部分情况跑不满，然后能卡过去要么数据太水要么 bitset 神力

by 快速数论变换 @ 2025-08-02 13:48:25

尽管 4\times 10^8 很大了，但跑不满啊，且现在机子都不很慢。

| 下一页