解题思路
给定一个上界 n(以二进制字符串给出)和 m 条限制。每条限制为一对 (p,o),表示:把 x 写成二进制(最低位下标从 0 计),则从低位起的第 p 位必须等于 o∈{0,1}。问区间 [0,n] 内满足所有限制的整数个数,答案对 998244353 取模。
关键观察:
- 若某个位置被要求既为 0 又为 1,或某条限制要求在 p≥L(L=len(n))的高位为 1,则不可能,答案为 0。因为对所有 x≤n,在第 p(≥L) 位一定为 0。
- 将限制先映射到长度为 L 的数组
need[i](下标从高位到低位)。
输入的 p 是从低位计数,换算为从高位的下标:i = L-1-p。若 i<0 或 i>=L 则是上面的越界情况。