Блог пользователя ducmatgoctoanlyhoa

A problem based on a Project Euler question
Автор ducmatgoctoanlyhoa, история, 20 месяцев назад, По-английски

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!

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
20 месяцев назад, скрыть # |
← Rev. 6  
Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить