I have a different solution with digit DP which does not require precomputation.
From the editorial we know below conclusions:
- the length of final array is at most \left\lfloor \log_2 M \right\rfloor + 1
- each bit only occurs on one element
- at most one element could equal to M
So we can define DP status as follow:
At bit k, dp[i] is the number of arrays with length i and have one element equal to the current binary prefix of M, and dp2[i] is the number of arrays with length i and have no element equal to the current binary prefix of M.
Traverse from highest bit to lowest bit, we can have below transitions:
- if the current bit of M is 0.
If we set no 1 to any element, this will not change the number of element equal to M.
Also, we can’t set this 1 on the element equal to M, so we have
dp[i] = dp[i]+dp[i]*(i-1)
dp2[i]=dp2[i]+dp2[i]*i - if the current bit of M is 1.
we can set 1 on any element, so we have
dp[i]=dp[i]
dp2[i]=dp[i]+dp2[i]+dp2[i]*i
Also, we can always add a new element 2^k if the current bit is k, so dp[1]+=1 if k is the most siginificant bit of M, otherwise dp2[i+1]+=dp[i]+dp2[i]
After finishing dp, we can calculate final result as below, because the order of elements could be rearranged freely:
ans=\Sigma_{i=1}^{60}{(dp[i]+dp2[i])}*i!
The time complexity is O(\log^2M) per testcase.