I also tried and failed, but I think my general idea was close.
Think of it like digit dp with dp[pos][tight][started]. DP is not necessary, but the ideas are useful. Considering started as an implementation detail, and pos as each bit, you can iterate downwards through the bits. Let's also define t as the number of bits greater than our pos which are in the x. Let us also assume tight is always true.
If the previous bit present in x is p, we can do some casework. If we select the next number to be at a bit in (pos+t, p] then the number will be greater no matter what the next bits are. For each number we can choose, we add w * 2^z to the final answer where z is the number of integers in [0,p] excluding our current number. w is the number of ways to reach this position(will be defined later).
If select the next number to be at a bit [0,pos+t), the number is smaller resulting in no solution.
Finally, the next number is equal to pos+t, the number is not guaranteed to be big enough but also not guaranteed to be too small. I defined w as the number of ways to reach this position. The transition is just w *= segtree[i]. This does not add anything to final answer, it just increases the number of ways for the case where the next bit is greater.
The final case(which I ran out of time for), is applying w at the end of a number. The value of w after going through all digits expresses the number of ways to hit exactly x. Based on p, you can consider every subset of future numbers(2^z where z = size of ([0,p]-1)), and then add it to the final answer.
I didn't get the problem, so I'm not sure, but this was my idea.
I also tried and failed, but I think my general idea was close.
Think of it like digit dp with dp[pos][tight][started]. DP is not necessary, but the ideas are useful. Considering started as an implementation detail, and pos as each bit, you can iterate downwards through the bits. Let's also define
tas the number of bits greater than ourposwhich are in thex. Let us also assumetightis always true.If the previous bit present in
xisp, we can do some casework. If we select the next number to be at a bit in(pos+t, p]then the number will be greater no matter what the next bits are. For each number we can choose, we addw * 2^zto the final answer wherezis the number of integers in [0,p] excluding our current number.wis the number of ways to reach this position(will be defined later).If select the next number to be at a bit
[0,pos+t), the number is smaller resulting in no solution.Finally, the next number is equal to
pos+t, the number is not guaranteed to be big enough but also not guaranteed to be too small. I definedwas the number of ways to reach this position. The transition is justw *= segtree[i]. This does not add anything to final answer, it just increases the number of ways for the case where the next bit is greater.The final case(which I ran out of time for), is applying
wat the end of a number. The value ofwafter going through all digits expresses the number of ways to hit exactlyx. Based onp, you can consider every subset of future numbers(2^zwherez= size of ([0,p]-1)), and then add it to the final answer.I didn't get the problem, so I'm not sure, but this was my idea.