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
Input3
1 1 1
4
1 2 3 4
5
5 4 3 1 2
What I've done
I have tried to solve this problem for an hour but when I submit it, many testcase is WA:
My verdictTest 1: OK, 0 point(s)
Group G1: 0.0 point(s)
Test 2: WRONG_ANSWER
Test 3: WRONG_ANSWER
Test 4: WRONG_ANSWER
Test 5: WRONG_ANSWER
Test 6: WRONG_ANSWER
Test 7: WRONG_ANSWER
Test 8: WRONG_ANSWER
Test 9: WRONG_ANSWER
Test 10: WRONG_ANSWER
Test 11: WRONG_ANSWER
Test 12: WRONG_ANSWER
Test 13: WRONG_ANSWER
Test 14: WRONG_ANSWER
Test 15: WRONG_ANSWER
Test 16: WRONG_ANSWER
Test 17: WRONG_ANSWER
Test 18: WRONG_ANSWER
Test 19: WRONG_ANSWER
Test 20: WRONG_ANSWER
Test 21: WRONG_ANSWER
Test 22: WRONG_ANSWER
Test 23: WRONG_ANSWER
Test 24: WRONG_ANSWER
Test 25: WRONG_ANSWER
Test 26: WRONG_ANSWER
Test 27: WRONG_ANSWER
Test 28: WRONG_ANSWER
Test 29: WRONG_ANSWER
Test 30: WRONG_ANSWER
Test 31: WRONG_ANSWER
Group G2: 0.0 point(s)
Test 32: WRONG_ANSWER
Test 33: WRONG_ANSWER
Test 34: WRONG_ANSWER
Test 35: WRONG_ANSWER
Test 36: WRONG_ANSWER
Test 37: WRONG_ANSWER
Test 38: WRONG_ANSWER
Test 39: WRONG_ANSWER
Test 40: WRONG_ANSWER
Test 41: WRONG_ANSWER
Test 42: WRONG_ANSWER
Test 43: WRONG_ANSWER
Test 44: WRONG_ANSWER
Test 45: WRONG_ANSWER
Test 46: WRONG_ANSWER
Test 47: WRONG_ANSWER
Test 48: WRONG_ANSWER
Test 49: WRONG_ANSWER
Test 50: WRONG_ANSWER
Test 51: WRONG_ANSWER
Test 52: WRONG_ANSWER
Test 53: WRONG_ANSWER
Test 54: WRONG_ANSWER
Test 55: WRONG_ANSWER
Test 56: WRONG_ANSWER
Test 57: WRONG_ANSWER
Test 58: WRONG_ANSWER
Test 59: WRONG_ANSWER
Test 60: WRONG_ANSWER
Test 61: WRONG_ANSWER
Test 62: WRONG_ANSWER
Test 63: WRONG_ANSWER
Test 64: WRONG_ANSWER
Test 65: WRONG_ANSWER
Test 66: WRONG_ANSWER
Test 67: WRONG_ANSWER
Test 68: WRONG_ANSWER
Test 69: WRONG_ANSWER
Test 70: WRONG_ANSWER
Test 71: WRONG_ANSWER
Test 72: WRONG_ANSWER
Test 73: WRONG_ANSWER
Test 74: WRONG_ANSWER
Test 75: WRONG_ANSWER
Test 76: WRONG_ANSWER
Test 77: WRONG_ANSWER
Test 78: WRONG_ANSWER
Test 79: WRONG_ANSWER
Test 80: WRONG_ANSWER
Test 81: WRONG_ANSWER
Test 82: OK
Test 83: OK
Test 84: OK
Test 85: OK
Test 86: OK
Test 87: OK
Test 88: OK
Test 89: OK
Test 90: OK
Test 91: OK
Test 92: OK
Test 93: OK
Test 94: OK
Test 95: OK
Test 96: OK
Test 97: OK
Test 98: OK
Test 99: OK
Test 100: OK
Test 101: OK
=
Points: 0.0
I don't know why my code failed, can you find out my mistake? This is my code.
My code#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define multitest int _T; cin >> _T; while (_T--)
const int MOD = 1000000007;
int add(int x, int y)
{
return (x + y) % MOD;
}
int mul(int x, int y)
{
return (x * y) % MOD;
}
void solve()
{
int n;
cin >> n;
int a[n];
int pre1[n+1];
pre1[0] = 0;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
pre1[i+1] = add(a[i], pre1[i]);
}
int pre2[n-1];
pre2[0] = 0;
for (int i = 1; i < n-1; ++i)
pre2[i] = add(pre2[i-1], mul(a[i], pre1[n] - pre1[i+1]));
int ans = 0;
for (int i = 0; i < n-2; ++i)
ans += mul(a[i], pre2[n-2] - pre2[i]);
cout << ans << endl;
}
signed main()
{
fastio;
multitest
solve();
}
Thank you in advance ❤️
sorry cnt help u bro
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.
Is that why when I transfer my code to Python, it causes Runtime error?
but,
pre1
is my prefix sum, whypre1[n] - pre1[i+1]
can be negative? (pre1[n]
is the last element in thepre1
array)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.
woah, thank you so much ❤️, I have understand it.
as you see my code on the post, how do I implement the mul() and add() correctly?
To implement them correctly just use
long long
(64-bit) type. Note that inmul
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 inint
(32-bit) type so the result ofmul
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 forlong long
type)Interesting fact: Let
Then the answer is just
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 ❤️
Can you explain how you got this result.Thanks
Well, in general, you only need to open the brackets:)
How did you derive the formula?
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
Obviously, there are all the summands of the condition, but there are also "extra" summands. Specifically, by opening the parentheses we get
Let's now calculate this sum
. Again by a similar trick we get that
(subtract from everything "extra")
Substituting in the first equality we get
So we find now
So we need to calculate only
and the answer is just
Of course here we will not divide by 6, but multiply by
This code is easy logic to understand and gets accepted :3
NOTE: it's clear that add mul is just using to take %mod.