ducmatgoctoanlyhoa's blog

A problem based on a Project Euler question
By ducmatgoctoanlyhoa, history, 20 months ago, In English

Hi! I am interested in evaluating this expression:

$$$\displaystyle{\sum_{i=1}^n (i * \text{popcount}(i))^2 \mod (10^9 + 7)}$$$

where $$$\text{popcount}(i)$$$ is the number of 1 digits in the binary expansion of $$$i$$$.

Or, in C++:

int mod = 1e9 + 7;
for (int i = 1; i <= n; ++i){
        // avoid calculating popcount more than once
        g = popcount(i);
        sum += a * a * g * g;
        sum %= mod;
    }
cout << sum;

The problem is that $$$N$$$ is very large ($$$10^{16}$$$). I am completely stuck, so thanks for your help!

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
20 months ago, hide # |
← Rev. 6  
Vote: I like it 0 Vote: I do not like it

This can be solved with digit dp.

dp[place][number of 1s in prefix][flag for max/min value] stores a pair (sum of all values in prefix, number)

//add a zero to the prefix
dp[i][j][0][0]+=dp[i-1][j][0][0] 
dp[i][j][0][1]+=dp[i-1][j][0][1]

//add a one to the prefix
dp[i][j+1][0][0]+=dp[i-1][j][0][0]+dp[i-1][j][0][1]*(1<<(bits-i-1))
dp[i][j+1][0][1]+=dp[i-1][j][0][1]

If the flag is set, you have to handle some edge cases and not run all the transitions based on the value of the number just as you would with any digit dp. (You could also avoid that by solving it for powers of 2, but that would have an extra log factor). Also obviously all the transitions should be done under mod.

The answer is the sum of dp[log(N)][j][flag][1]*j^2 over all j in 1...log(N).

→ Reply