Python 3 has unlimited size integers, which can function as dynamic size bitsets when doing bitwise operations. Python is still about 3x slower than C++ bitsets with no pragmas and 10x slower than C++ with avx2+O3 pragmas. However, the Python integers have dynamic size, so there some potential of making a problem that requires dynamic bitsets purely to mess with people who use C++ standard library bitsets.
Anyways, here's some simple code I wrote in Python for https://ecna22.kattis.com/problems/amusicalquestion. It is AC in 0.16s.
Code









AFAIK, there is
std::tr2::dynamic_bitsetin (and I believe, only in) GCC (reference link here). I think it is to replacestd::vector<bool>in a near future, but it is not yet in the standards. It is at least in a "usable" state if I remember correctly.There's a simple way to use static bitsets (with minimal overhead) when dynamic bitsets are needed.
And if you want to limit $$$N$$$ to a certain limit, you can do it using
std::enable_if(now you can even usesize_twithout warnings):And if you want to be more space efficient about it, consider replacing
2 * Nbystatic_cast<uint32_t>(1.5 * N + 1)or something similar everywhere, though the smaller the increase, the more functions andifchecks there will be. In the worst case, if the increase is linear, you'll either have a bloated binary (with potential instruction cache misses) or the compiler will fail to compile the code due to out of memory errors, not to mention the linear search time in this recursive definition.Is this a certified way to do bitset in python?
I found python 1 << k can hold 1000 number of bits. Not sure how to do count, any, iterating all 1's in constant time as C++ ? https://leetcode.com/problems/all-paths-from-source-lead-to-destination/submissions/1458994019/?envType=problem-list-v2&envId=topological-sort
for
count(), you can do like__builtin_popcount()in c++ in $$$\mathcal O(\frac{N}{w})$$$:for
any()just see if it's 0.for iterating all 1s you can use lowbit (count()) times: