一个 bitset 值 52 分？
首先样例让你容斥你就容斥，枚举哪些位是可以的，计算每一位的 \(p_0,p_1,q_0,q_1\) 表示是否被要求最后是 \(0/1\)，是否有最终值是开始值异或 \(0/1\)。然后每个位置的贡献可以分类讨论出来：
- 如果 \(p_0,p_1\) 或者 \(q_0,q_1\) 都有，那只能空着。
- 如果 \(p_0,p_1\) 中有一个且 \(q_0,q_1\) 中有一个，那除了空着还有恰好一种方法。
- 否则都可以填。
这样可以得到一个 \(O(2^n\operatorname{poly}(nm))\) 的做法，期望得分 \(28\)。
\(n\) 这么小考虑根号分治，按照第一种容斥暴力枚举前 \(\frac{n}{2}\) 位。如果后 \(\frac{n}{2}\) 位有值，说明向右走的步数不超过 \(\frac{n}{2}\)，计算某个位置的贡献时有用的也就只有前 \(\frac{n}{2}\) 位。
考虑 dp，先枚举最后一位在哪里，然后设 \(dp_{i,S}\) 表示到了第 \(i\) 位，前面 \(\frac{n}{2}\) 位是 \(S\)。平衡可以得到一个 \(O(2^{\frac{n}{2}}n^2m)\) 的做法，大概能过 \(48\) 分。
主要的瓶颈在于计算贡献。首先是可以 bitset 优化，变成 \(O(\frac{2^{\frac{n}{2}}n^2m}{\omega})\)，然后我们发现我们实际上要求的是一个子集异或的形式，所以可以每次分成刨掉最低位和最低位或起来，这样可以优化到 \(O(\frac{2^{\frac{n}{2}}nm}{\omega})\)，就稳过了。
标签：P7740,frac,luogu,可以,容斥,NOI2021,枚举,dp From： https://www.cnblogs.com/275307894a/p/17481371.html