brownfox2k6's blog

[Nested Sum] Can you help me with this problem?
By brownfox2k6, history, 21 month(s) ago, In English

Problem source

104168D2 - Nested Sum (Hard Version)

Statement

Given an array of $$$n$$$ positive integers $$$a_{1}, a_{2},...,a_{n}$$$, find the value of $$$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=j+1}^{n}a_{i}a_{j}a_{k}$$$ modulo $$$10^{9}+7$$$

Input

The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$).

The first line of each test case contains an integer $$$n$$$ ($$$1 \le t \le 10^{5}$$$), the size of the array.

The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2},...,a_{n}$$$ ($$$1 \le t \le 10^{9}$$$), the elements of the array.

The sum of n over all test cases doesn't exceed $$$5\cdot 10^{5}$$$.

Output

For each test case output one line containing one integer, the sum described in the problem modulo $$$10^{9}+7$$$

Example

Input
Output

What I've done

I have tried to solve this problem for an hour but when I submit it, many testcase is WA:

My verdict

I don't know why my code failed, can you find out my mistake? This is my code.

My code

Thank you in advance ❤️

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

Comments Comments (15)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

sorry cnt help u bro

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

The problem is on line 38 with pre1[n] - pre1[i+1]. This value might be negative. You want all numbers to lie between 0 and MOD-1. You can modify add function to handle negative values which is giving AC.

But, I would recommend you to use modint templates because it is easier and cleaner.

Code with modint template
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is that why when I transfer my code to Python, it causes Runtime error?

    Verdict
    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    but, pre1 is my prefix sum, why pre1[n] - pre1[i+1] can be negative? (pre1[n] is the last element in the pre1 array)

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because you are taking it modulo a number. Let's say mod was 5 and the array was [3,4]. Then pre1 would be [0,3,(3+4)%5=2]. Then pre[2]-pre[1] will be -1.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        woah, thank you so much ❤️, I have understand it.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    as you see my code on the post, how do I implement the mul() and add() correctly?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To implement them correctly just use long long (64-bit) type. Note that in mul function you first multiply two ints and then get the result modulo $$$10^9+7$$$. $$$10^9 \cdot 10^9 = 10^{18}$$$ — doesn't fit in int (32-bit) type so the result of mul function may be wrong due to overflow. If you use 64-bit type you will get a correct result since any product will be $$$\le (10^9+7-1)^2 < 2^{63}-1$$$ (max value for long long type)

      → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Interesting fact: Let

$$$A = \sum_{i=1}^n x_i \\B = \sum_{i=1}^n x_i^2\\C = \sum_{i=1}^n x_i^3$$$

Then the answer is just

$$$\frac{A^3 - 3(AB - C) - C}{6}$$$
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    wow... I spent 2 hours thinking the way to implement the prefix sum and then you give me a simple equation. I realized I have a lot of things to improve. Thank you so much ❤️

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Can you explain how you got this result.Thanks

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, in general, you only need to open the brackets:)

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you derive the formula?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      Okay. First, there is a wonderful theorem (https://brilliant.org/wiki/symmetric-polynomials-definition/). It is not quite what you need — but it gives an understanding of how the problem should be solved. (You can search for better articles, I found it in English). Now about how to come up with this solution. Let's look at the expression

      $$$A = (\sum_{i=1}^n x_i)^3$$$

      Obviously, there are all the summands of the condition, but there are also "extra" summands. Specifically, by opening the parentheses we get

      $$$A = (\sum_{i=1}^n x_i)^3 = 6*(sum \; we \;need \;to\; calculate) + \sum_{i=1}^n x_i^3 + 3*\sum_{i=1}^n \sum_{j=i+1}^n x_i^2 x_j $$$

      Let's now calculate this sum

      $$$T = 3*\sum_{i=1}^n \sum_{j=i+1}^n x_i^2 x_j $$$

      . Again by a similar trick we get that

      $$$B = 3*\sum_{i=1}^n \sum_{j=i+1}^n x_i^2 x_j = 3*(\sum_{i=1}^n x_i^2)*( \sum_{i=1}^n x_i) - 3*\sum_{i=1}^n x_i^3$$$

      (subtract from everything "extra")

      Substituting in the first equality we get

      $$$A = (\sum_{i=1}^n x_i)^3 = 6*(sum \; we \;need \;to\; calculate) + \sum_{i=1}^n x_i^3 + 3*(\sum_{i=1}^n x_i^2)*( \sum_{i=1}^n x_i) - 3*\sum_{i=1}^n x_i^3$$$

      So we find now

      $$$sum \; we \;need \;to\; calculate = \frac{(\sum_{i=1}^n x_i)^3 - \sum_{i=1}^n x_i^3 - 3*(\sum_{i=1}^n x_i^2* \sum_{i=1}^n x_i - \sum_{i=1}^n x_i^3)}{6}$$$

      So we need to calculate only

      $$$\sum_{i=1}^n x_i \;\;\;B = \sum_{i=1}^n x_i^2\;\;\;C=\sum_{i=1}^n x_i^3$$$

      and the answer is just

      $$$\frac{A^3 - C - 3(AB-C)}{6}$$$

      Of course here we will not divide by 6, but multiply by

      $$$(1/6) \;\;mod \;(1e9+7)$$$
      → Reply
»
19 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This code is easy logic to understand and gets accepted :3

NOTE: it's clear that add mul is just using to take %mod.

    int ans = 0, suf_sum = 0, sufP = 0;
    for (int i = n &mdash; 1; i >= 0; --i) {
        // ans += a[i]*suf pairs
        ans = add(ans, mul(a[i], sufP));
        // suf pairs += a[i]*suffix
        sufP = add(sufP, mul(a[i], suf_sum));
        // suffix = summation of passed elements
        suf_sum = add(suf_sum, a[i]);
    }
→ Reply