Note) The answer example is only Python3 </ b>. For C ++ and Java, it is recommended to see the code from "All submissions" and implement it.
Hi everyone (who after the contest Good evening!) Is Rute!
AtCoder Beginner Contest 177 C We're about to start explaining the problem! You can see the explanation of problems A and C from the links below, so please check! !!
| A problem | B problem | C problem |
|---|---|---|
| in preparation | in preparation | This article |
Given a sequence of $ N $ integers $ A_1, ... A_N $. Find the sum of $ A_i × A_j $ for all pairs $ (i, j) $ that satisfy $ 1 \ leq i <j \ leq N $ with $ mod (10 ^ 9 + 7) $.
Problem URL: https://atcoder.jp/contests/abc177/tasks/abc177_c
・ $ 2 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 0 \ leq A_i \ leq 10 ^ 9 $ ・ All inputs are integers
Of $ A_1, ... A_N $, the $ (i, j) $ pair is $ (N-1) + (N-2) + .... 1 $ pair, and $ \ frac {N (N (N) You can see that there are -1)} {2} $ pairs. If you think about these $ 1 $ pieces and calculate, you will need the amount of calculation of $ O (N ^ 2) $. Generally, the number of calculations that a computer can process per second is about $ 10 ^ 8 $ (100 million times), so due to restrictions, this amount of calculation will exceed the execution time limit </ b>.
Now let's consider the problem from a different perspective.
In Input Example 1 and Output Example 1, the answer is $ 11 $,
About the answer
\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j
I know that
So, first, let's think about finding $ \ sum_ {j = i + 1} ^ {N} A_j $.
The technique used here is called cumulative sum </ b> </ font>.
Cumulative sum is to find the sum from the first term to a certain term in advance and make a sequence about it.
As an example of the sequence created by the cumulative sum,
Given the sequence $ B
For details, see Kenchon-san's Cumulative Sum Article.
The cumulative sum we consider this time is a sequence of length $ N-1 $.
You now have a sequence of $ \ sum_ {j = i + 1} ^ {N} A_j $. Let's call this sequence $ C $.
next,
\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j
Calculate $ A_i x C_i $ for each $ i (1 \ leq i \ leq N-1) $ to find. Add that value to the value of the answer you are looking for.
Finally, divide the answer value by $ (10 ^ 9 + 7) $ and output the remainder.
Here, in the case of Python, it is not necessary to divide the answer by $ (10 ^ 9 + 7) $ each time because it corresponds to multiple-precision integers, but in the case of C ++ and Java, it is in the middle of calculation. The answer may be larger than the 64-bit integer range. </ b> (long, long long int, etc.) (so-called overflow </ b>)
This is because $ 2 ^ {63} -1 \ simeq 9.22 × 10 ^ {18} $, but due to the constraint of $ A_i $, it is possible that $ 10 ^ {18} $ may be added more than $ 10 $ times. is.
After all, even if you continue to divide the value by $ 10 ^ 9 + 7 $ each time after adding it, it will be the same in the end, so if you continue to divide it by $ 10 ^ 9 + 7 $, overflow You don't have to worry about </ b>.
The amount of calculation is $ O (N) $ in the cumulative sum processing, and it costs $ O (1) $ when calculating $ A_i × C_i $ for each $ i (1 \ leq i \ leq N-1) $ It becomes $ O (N) $.
The following is an example of the answer in Pyhton3, C ++, Java. (As of 8/30 11:29, only the answer example of Python3 is shown. C ++ and Java will be created as soon as they are ready, so please wait for the update.)
{ABC177C.py}
N = int(input()) #Integer to enter
A = list(map(int,input().split())) #Sequence A to enter
SUMA = sum(A) #The sum of the sequence
MOD = 10**9 + 7 # mod
C = [0] * (N-1) #Cumulative sum sequence
for i in range(N-1): #\sum_{j = i+1}^{N}To find and assign to a sequence of numbers
SUMA -= A[i]
C[i] = SUMA
ans = 0 #The answer you seek
for i in range(N-1):
ans += A[i]*C[i]
ans %= MOD #Divide by mod each time
print(ans) #Output the answer
#Computational complexity is O(N)is.
in preparation
in preparation
Recommended Posts