If there is no \(+1\) in the operation, it’s a quite standard problem and can be solved by FWT in \(O(n2^n)\) time.

Now with the \(+1\), since we are only adding \(1\) at a time, it’s easy to see that the carry will be done only in a suffix. More precisely, every time we do the \(+1\), there will exist some \(k\) such that the last \(k\) bits of \(x\) are all \(1\). Then we make them \(0\) and set the \(k+1\)-th bit to \(1\).

First, we consider all the operations where \(k\ge 1\), which means that the last bit is \(1\) in that operation.

Between two such operations, no carry is done at all, so for all bits except the last, we are simply doing the bitwise or operation. For an operation with \(k\ge 1\), we can think of it as “setting the last bit to \(0\), and adding \(1\) to the previous bits as a whole”. Note that this applies even if \(k>1\), since “adding \(1\) as a whole” can also make new carries.

Next we try to calculate \(f_i\) representing the number of ways to start from \(0\), and make the value of the bits except for the last one equal to \(i\), while only making a carry in the last operation from the last bit.

It’s easy to see that such operation sequences can only consist of \(1\) or \(2\) moves. We can either choose some \(s_i\) with the last bit equal to \(1\) and finish in one move, or choose \(s_i,s_j\) in this order with the last bit of \(s_i\) equal to \(0\) and finish in two moves. Since the impact of the operations to higher bits without carry is simply bitwise or, we can use FWT to calculate all \(f_i\) in \(O(n2^n)\) time.

Recall the meaning of \(f_i\), and we can realize that we are in the exact same subproblem without the last bit. More specifically, \(f_i\) represents the number of ways to make one carry to the second last bit, and setting the last bit to \(0\). Since at the end \(x=2^n\) does indeed have \(0\) as its last bit, we can break the operations into groups, where every group provides exactly one carry to the second last bit.

Therefore, if we now erase the last bit, we can reform the problem as “for every operation, choose any \(i\) and set \(x\) to \((x\text{ OR } i)+1\) with \(f_i\) choices”. Here \(f_i\) is simply a coefficient belonging to \(i\). It’s easy to see that this problem is exactly the same as before, with \(n-1\) as the number of bits now. So we can calculate new \(f_i\) in the same way, and move on to the next subproblem.

For the time complexity, we need to do FWT once for each \(i=0,1,\cdots,n-1\), so the total time complexity is \(O(n2^n)\). Surprisingly, it runs much faster than most of the other solutions.

code