ducmatgoctoanlyhoa's blog

A problem based on a Project Euler question
By ducmatgoctoanlyhoa, history, 5 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

question link pls

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi! when solving this issue, I suggest that you use modular multiplication. What you're trying to do is a simple multiplication followed by a modulo multiplication. // sum += a * a * g * g; sum %= mod; The problem occurs when a * b can exceed the range of standard data types (for example long long), so we use methods to avoid overflow. in c++ it looks like this:

long long ans(long long a, long long b, long long mod) {
    return (a % mod) * (b % mod) % mod;
}

so your code will looks like this:

sum += ans(ans(a, a, mod), ans(g, g, mod), mod);
sum %= mod;

I think this will work with 10^16

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! That's the least of my worries though, the real problem is the $$$N = 10^{16}$$$...

    → Reply
»
4 weeks ago, # |
← 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