Problem:


Score : 800 points

Problem Statement

Let’s take a prime P = 200\,003.
You are given N integers A_1, A_2, \ldots, A_N.
Find the sum of ((A_i \cdot A_j) \bmod P) over all N \cdot (N-1) / 2 unordered pairs of elements (i < j).

Please note that the sum isn't computed modulo P.

Constraints

2 \leq N \leq 200\,000

0 \leq A_i < P = 200\,003

All values in input are integers.

Input

Input is given from Standard Input in the following format.

N
A_1 A_2 \cdots A_N

Output

Print one integer — the sum over ((A_i \cdot A_j) \bmod P).

Sample Input 1

4
2019 0 2020 200002

Sample Output 1

474287

The non-zero products are:

2019 \cdot 2020 \bmod P = 78320

2019 \cdot 200002 \bmod P = 197984

2020 \cdot 200002 \bmod P = 197983

So the answer is 0 + 78320 + 197984 + 0 + 0 + 197983 = 474287. 

Sample Input 2

5
1 1 2 2 100000

Sample Output 2

600013



Sample input:
4
2019 0 2020 200002


Sample output:
474287

Submission status: Wrong Answer

Solution code:
# Coding is about expressing your feeling and there is always a better way to express your feeling _feelme
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(arr, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if arr[mid] == val:return mid
        elif arr[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,arr):
    for i in range(1,n):arr[i]+=arr[i-1]
    return arr;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
# @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ code here @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
mod=200003
n = ii1()
arr = iia()
s=0
dp=[0]*(n)
cache=0
modd=mod
for i in range(n-1,-1,-1):
    s+=arr[i]
    dp[i]=s
# print(dp)
ans=0
for i in range(n-1):
    ans+=((arr[i])*(dp[i+1]))%mod
cache+=ans//mod
print(ans+mod*cache)

'''
474287
'''

Submission status: Wrong Answer

Solution code:
# Coding is about expressing your feeling and there is always a better way to express your feeling _feelme
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(arr, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if arr[mid] == val:return mid
        elif arr[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,arr):
    for i in range(1,n):arr[i]+=arr[i-1]
    return arr;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
# @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ code here @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
mod=200003
n = ii1()
arr = iia()
s=0
dp=[0]*(n)
cache=0
modd=mod
for i in range(n-1,-1,-1):
    s+=arr[i]
    dp[i]=s
# print(dp)
ans=0
for i in range(n-1):
    ans+=((arr[i])*(dp[i+1]))%mod
    cache+=ans//mod
print(ans+mod*cache)

'''
474287
'''

Submission status: Wrong Answer

Solution code:
# Coding is about expressing your feeling and there is always a better way to express your feeling _feelme
import sys,math
try:sys.stdin,sys.stdout=open('input.txt','r'),open('out.txt','w')
except:pass
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt,log
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(arr, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if arr[mid] == val:return mid
        elif arr[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,arr):
    for i in range(1,n):arr[i]+=arr[i-1]
    return arr;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;
# @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ code here @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
mod=200003
n = ii1()
arr = iia()
s=0
dp=[0]*(n)
cache=0
modd=mod
for i in range(n-1,-1,-1):
    s+=arr[i]
    dp[i]=s
# print(dp)
ans=0
for i in range(n-1):
    ans+=((arr[i])*(dp[i+1]))%mod
print(ans+mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = []
for i in input().split():
	if int(i)%200003 == 0:
		pass
	else:
		a.append(int(i))
cnt = 0
for i in range(len(a)):
	for j in range(i+1,len(a)):
			cnt += (a[i]*a[j])

print(cnt)

Submission status: Wrong Answer

Solution code:

n,ais = int(raw_input()), map(int, raw_input().split())
cumul = 0 
p = 200003

for i in range(len(ais)):
	q = 0
	prev = 0
	if ais[i]:
		for j in range(i+1, len(ais)):
			if ais[j] - prev > 0:
				q += ais[i] * (ais[j] - prev)
				q %= p
				prev = ais[j]
			cumul += q 
print cumul

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0
A2 = 0

B = sum(A)**2
for i in range(len(A)):
    A2 += A[i]**2

print(int(((B-A2)/2)%mod + mod*(((B-A2)/2)//mod)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0
A2 = 0

B = sum(A)**2
for i in range(len(A)):
    A2 += A[i]**2

print((int(((B-A2)/2)))%mod + mod*(((B-A2)/2)//mod))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))
C = Counter(A)

mod = 200003

table = [0]*mod
for a, v in C.items():
    if not a:
        continue
    for i in range(1, mod):
        j = -((-i*mod)//a)
        if j >= mod:
            break
        table[j] += 1

for i in range(1, mod):
    table[i] += table[i-1]

geta = 0
for a, v in C.items():
    geta += v*table[a]

sa = sum(A)**2
tt = sa - geta*mod
#print(tt)
for a in A:
    tt -= a*a%mod

print(tt//2)

"""
cnt = 0
for a in A:
    for b in A:
        cnt += a*b%mod

print(cnt)
"""

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 200003
ans = 0
A2 = 0

B = sum(A)**2
for i in range(len(A)):
    A2 += A[i]**2

print(int(((B-A2)/2)%(mod**2)))

Submission status: Wrong Answer

Solution code:
#

Submission status: Wrong Answer

Solution code:
N=int(input())
x=list(map(int, input().split()))
re=0
for i in range(N-1):
  z=1
  while True:
    re=re+x[i]*x[i+z]%200003
    if x[i+z]==x[-1]:
      break
    z+=1
print(re)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


n = int(readline())
A = np.array(read().split(), np.int64)
mod = 200003

fft_len = 2 * 10 ** 5

x = irfft(rfft(A, fft_len) * rfft(A, fft_len))
x = (x[: n * n] + 0.5).astype(int)
x //= 2
x %= mod
y = A * A
y //= 2
y %= mod
print(x.sum() - y.sum())

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
i = 0
j = 1
s = 0
for i in range (N - 1):
    for i in range (j):
        if not A[i] == 0 and not A[j] == 0: 
            s = s + A[i] * A[j]
        i = i + 1
    i = 0
    j = j + 1
print(s)

Submission status: Wrong Answer

Solution code:
N=int(input())
data_pre=input().split()
data=[int(s) for s in data_pre]
data_mod=[]
ans=0
for i in range(N):
    data_mod.append(data[i]%200003)
data_str=list(set(data_mod))
data_str_ind=[]
for i in range(len(data_str)):
    data_str_ind.append(data_mod.count(data_str[i]))
for i in range(len(data_str)-1):
    for j in range(i+1,len(data_str)):
        ans+=((data_str[i]*data_str[j])%200003)*data_str_ind[i]*data_str_ind[j]
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int, input().split()))
t=0
for i in range(0,n-1):
    for j in range(i+1,n):
        t = t + (a[i]*a[j])%200003
        print((a[i]*a[j])%200003)
print(t)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

P = 200003

# 整数の入力
a = int(input())
 
# 浮動小数点の入力
num_list = list(map(int, input().split())) 

sum = 0
for i in num_list:
  for j in num_list:
    if i < j:
      sum += i * j % P
 
# 出力
print("{}".format(sum))

Submission status: Time Limit Exceeded

Solution code:
class Convolution:
  def __init__(s, MOD):
    s.MOD = MOD
    s.PrimitiveRoot = s.primitive_root(MOD)
    s._BIT_TABLE = [0] * 64
    _BIT_HASH = 0x03F566ED27179461
    for i in range(64):
      s._BIT_TABLE[_BIT_HASH >> 58] = i
      _BIT_HASH <<= 1
      _BIT_HASH &= 0xFFFFFFFFFFFFFFFF

  def convolution(s, a, b):
    n, m = len(a), len(b)
    if not n or not m: return []
    if min(n, m) <= 60:
      if n < m:
        n, m = m, n
        a, b = b, a
      ans = [0] * (n + m - 1)
      for i in range(n):
        for j in range(m):
          ans[i + j] = (ans[i + j] + a[i] * b[j]) % s.MOD
      return ans
    z = 1 << s.ceil_pow2(n + m - 1)
    a = a + [0] * (z - n)
    a = s.butterfly(a)
    b = b + [0] * (z - m)
    b = s.butterfly(b)
    for i in range(z): a[i] = a[i] * b[i] % s.MOD
    a = s.butterfly_inv(a)
    iz = pow(z, s.MOD - 2, s.MOD)
    for i in range(n + m - 1): a[i] = a[i] * iz % s.MOD
    return a[:n + m - 1]

  def convolution_ll(s, a, b):
    n, m = len(a), len(b)
    if not n or not m: return []
    # 64bitに収める
    B = pow(2, 64)
    MOD1 = 754974721
    MOD2 = 167772161
    MOD3 = 469762049
    M2M3 = MOD2 * MOD3 % B
    M1M3 = MOD1 * MOD3 % B
    M1M2 = MOD1 * MOD2 % B
    M1M2M3 = MOD1 * MOD2 * MOD3 % B
    i1 = s.inv_gcd(MOD2 * MOD3, MOD1)[1]
    i2 = s.inv_gcd(MOD1 * MOD3, MOD2)[1]
    i3 = s.inv_gcd(MOD1 * MOD2, MOD3)[1]
    conv1 = Convolution(MOD1)
    conv2 = Convolution(MOD2)
    conv3 = Convolution(MOD3)

    c1 = conv1.convolution(a, b)
    c2 = conv2.convolution(a, b)
    c3 = conv3.convolution(a, b)

    c = [0] * (n + m - 1)

    for i in range(n + m - 1):
      x = 0
      x += (c1[i] * i1) % MOD1 * M2M3 % B
      x = (x + (c2[i] * i2) % MOD2 * M1M3) % B
      x = (x + (c3[i] * i3) % MOD3 * M1M2) % B
      diff = c1[i] - (x % MOD1)
      if diff < 0: diff += MOD1
      offset = [0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3]
      x -= offset[diff % 5]
      c[i] = x
    return c

  def safe_mod(s, x, m):
    x %= m
    if x < 0: x += m
    return x

  def butterfly(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_e = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_e[i] = es[i] * now % s.MOD
        now = now * ies[i] % s.MOD
    for ph in range(1, h + 1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      now = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p] * now % s.MOD
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (l - r) % s.MOD
        now = now * sum_e[s.bsf(~ss)] % s.MOD
    return a

  def butterfly_inv(s, a):
    g = s.PrimitiveRoot
    n = len(a)
    h = s.ceil_pow2(n)

    first = True
    sum_ie = [0] * 30
    if first:
      first = False
      es, ies = [0] * 30, [0] * 30
      cnt2 = s.bsf(s.MOD - 1)
      e = pow(g, ((s.MOD - 1) >> cnt2), s.MOD)
      ie = pow(e, s.MOD - 2, s.MOD)
      for i in range(cnt2, 1, -1):
        es[i - 2] = e
        ies[i - 2] = ie
        e = e * e % s.MOD
        ie = ie * ie % s.MOD
      now = 1
      for i in range(cnt2 - 2):
        sum_ie[i] = ies[i] * now % s.MOD
        now = now * es[i] % s.MOD
    for ph in range(h, 0, -1):
      w, p = 1 << (ph - 1), 1 << (h - ph)
      inow = 1
      for ss in range(w):
        offset = ss << (h - ph + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p]
          a[i + offset] = (l + r) % s.MOD
          a[i + offset + p] = (s.MOD + l - r) * inow % s.MOD
        inow = inow * sum_ie[s.bsf(~ss)] % s.MOD
    return a

  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

  def bsf(s, n):
    if n == 0: return 64
    x = n
    y = x & -x
    i = ((y * 0x03F566ED27179461) & 0xFFFFFFFFFFFFFFFF) >> 58
    return s._BIT_TABLE[i]

  def prime(s, x):
    L, U = [], []
    i = 1
    while i * i <= x:
      if x % i == 0:
        L.append(i)
        if i != x // i:
          U.append(x // i)
      i += 1
    return L + U[::-1]

  def primitive_root(s, x):
    L = s.prime(x - 1)
    a, i = 2, 0
    k = len(L) - 1
    while i != k:
      if pow(a, L[i], x) == 1:
        a += 1
        i = 0
      else:
        i += 1
    return a

  def inv_gcd(s, a, b):
    a %= b
    if a == 0: return (b, 0)
    v, t = b, a
    m0, m1 = 0, 1
    while t:
      u = v // t
      v -= t * u
      m0 -= m1 * u
      v, t = t, v
      m0, m1 = m1, m0
    if m0 < 0: m0 += b // v
    return (v, m0)

N = int(input())
a = list(map(int, input().split()))
MOD = 200003

r = 2
EXP = [0] * MOD
LOG = [0] * MOD
EXP[0] = 1
# r ^ i % MOD = EXP[i]
# logr(i) = LOG[i]
for i in range(1, MOD):
  EXP[i] = EXP[i - 1] * r % MOD
  LOG[EXP[i]] = i

b = [0] * MOD
for n in a:
  # log0は無限、実際には不要なので無視
  if n == 0: continue 
  b[LOG[n]] += 1

conv = Convolution(MOD)

# x * y = z => log(x * y) = log(z) => log(x) + log(y) = log(z)
# c[i] <- log(x) + log(y) が i となる個数
c = conv.convolution_ll(b, b)

ans = 0
t = 1
for n in c:
  # log(z)をzに戻しつつ個数を掛ける
  ans += n * t
  t = t * r % MOD

# i * i が含まれているので引く
for i in a:
  ans -= i * i % MOD

# i * j と j * i が両方含まれているので割る
ans //= 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=int(1e9)+7
P=200003
###############################################################################\n=17
n=int(input())
A=INPUT()
sum=0
for i in range(n):
    for j in range(i+1,n):
        sum+=(A[i]*A[j])%P
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = 200003
lst = list(map(int,input().split()))
lst_product = []
count = 0
for i in range(N):
    for j in range(i+1,N):
        count += (lst[i]*lst[j]) % P
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = 200003
lst = list(map(int,input().split()))
lst_product = []
count = 0
for i in range(N):
    for j in range(i+1,N):
        product = lst[i]*lst[j]
        count += product % P
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = 200003
lst = list(map(int,input().split()))
lst_product = []
for i in range(N):
    for j in range(i+1,N):
        product = lst[i]*lst[j]
        lst_product.append(product)
count = 0
for i in range(len(lst_product)):
    count += lst_product[i] % P
print(count)

Submission status: Time Limit Exceeded

Solution code:
#QN = map(int,input().split()) # 500
N = int(input())

vals = []
#for i in range(N):
#  list.append(input())
vals = list(map(int,input().split()))

no = 1
cnt =0
total = 0
P = 200003
for val in vals:
  for j in vals[no:]:
    total += ((val * j) % P)
    
  no += 1

print("{}".format(total))

Submission status: Time Limit Exceeded

Solution code:
#QN = map(int,input().split()) # 500
N = int(input())

vals = []
#for i in range(N):
#  list.append(input())
vals = list(map(int,input().split()))

no = 1
cnt =0
total = 0
P = 200003
for val in vals:
  for j in range(N-no):
    total += ((val * vals[no+j]) % P)
    
  no += 1

print("{}".format(total))

Submission status: Time Limit Exceeded

Solution code:
#QN = map(int,input().split()) # 500
N = int(input())

list = []
#for i in range(N):
#  list.append(input())
a = map(int,input().split())

for val in a:
  list.append(val)
#list = int(input().split()) 

no = 1
cnt =0
total = 0
P = 200003
for i in range(N):
  for j in range(N-no):
    total += ((list[i] * list[no+j]) % P)
    
  no += 1

print("{}".format(total))

Submission status: Time Limit Exceeded

Solution code:
import math

class FastFourierTransform:

	def dft(self, F, inverse ):
		N = len(F)
		if N==1:
			return

		f0 = [ F[2*n] for n in range(N // 2) ]
		f1 = [ F[2*n+1] for n in range(N // 2) ]

		self.dft(f0, inverse)
		self.dft(f1, inverse)

		# 最初のzetaは1
		now = 1 + 0j
		# polar(1.0, inverse * 2.0 * acos(-1) / sz)
		# 絶対値,偏角[rad]
		#zeta = crect(1.0, inverse * 2.0 * acos(-1) / N )
		zeta = complex(math.cos( inverse * 2.0 * math.pi / N ), math.sin( inverse * 2.0 * math.pi / N ) )

		for n in range(N):
			F[n] = f0[ n % (N//2) ] + now * f1[ n % (N//2) ]
			now *= zeta

	def multiply(self, F,G):
		""" multiply by FFT
		"""
		N=1
		# 1.N > deg(g) + deg(h)となる2の冪乗を選ぶ
		while N < len(F) + len(G):
			N *= 2
		# 2. 離散フーリエ変換の計算
		nf = F + [0] * (N-len(F))
		ng = G + [0] * (N-len(G))

		# print("start dft")
		self.dft( nf, 1 )
		self.dft( ng, 1 )
		# print("end dft")
		for n in range(N):
			nf[n] *= ng[n]

		# 3. 離散フーリエ逆変換
		self.dft( nf, -1 )

		ans = []
		for n in range(N):
			# 係数を1/N倍
			ans.append( round(nf[n].real / N) )

		return ans

if __name__ == "__main__":
	N=int(input())
	A=list(map(int,input().split()))

	P=200_003
	rootP=2

	# order of 1 to P-1 after fft
	order=[1]
	x=rootP
	while x!=1:
		order.append(x)
		x *= rootP
		x %= P

	ORDER_SIZE=len(order)	# 200_002

	# create order index
	where=[0 for _ in range(P)]
	for i in range(ORDER_SIZE):
		where[ order[i] ] = i

	# count non zero items
	prevCnt1 = [ 0 for _ in range(P)]
	prevCnt2 = [ 0 for _ in range(P)]
	resCnt = [ 0 for _ in range(P)]
	for n in range(N):
		if A[n] != 0:
			prevCnt1[ where[A[n]] ] += 1
			prevCnt2[ where[A[n]] ] += 1
			# remove Ax * Ax pattern count
			resCnt[ (A[n] * A[n]) % P ] -= 1

	# fft to cnt (calc nC2 and all Ax * Ay)
	clsFFT = FastFourierTransform()
	fftRes = clsFFT.multiply(prevCnt1,prevCnt2)

	for r in range(len(fftRes)):
		if fftRes[r] != 0:
			# get result(Ax*Ay==resCnt.index) Cnt by summary fftRes
			resCnt[ order[ r % ORDER_SIZE ] ] += fftRes[r]

	ans = 0
	for p in range(P):
		if resCnt[p] != 0:
			# print(p,resCnt[p])
			# remove j <= i pattern count 
			# and
			# calc summary value((Ax * Ay cnt) * (Ax * Ay)))
			ans += (resCnt[p] // 2) * p

	print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def load():
    num = int(input())
    line = input()

    numbers = map(lambda s: int(s), line.split())
    return list(numbers)


def get_pair(array):
    num = len(array)

    for i in range(num - 1):
        for j in range(i + 1, num):
            yield (array[i], array[j])

if __name__ == "__main__":
    numbers = load()
    counter = 0
    prime = 200003

    x = [(n1 * n2) % prime for n1, n2 in get_pair(numbers)]
    print(sum(x))

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 200003
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def dft(f,n,sign=1):
    if len(f) != n:
        f += [0]*(n-len(f))
    if n == 1:
        return f
    f0 = dft(f[0::2],n//2,sign)
    f1 = dft(f[1::2],n//2,sign)
    zeta = complex(math.cos(2*math.pi/n),sign*math.sin(2*math.pi/n))
    pow_zeta = 1
    for i in range(n):
        f[i] = f0[i%(n//2)] + pow_zeta*f1[i%(n//2)]
        pow_zeta *= zeta
    return f

def multiply(g,h):
    n = 2**len(format((len(g)+len(h)+1),'b'))
    g += [0]*(n-len(g))
    h += [0]*(n-len(h))
    gg = dft(g,n)
    hh = dft(h,n)
    ff = [gi*hi for gi,hi in zip(gg,hh)]
    ff = dft(ff,n,-1)
    gh = [int(ffi.real/n+0.1) for ffi in ff]
    return gh

def main():
    n = int(ipt())
    g = 2
    order = [1]
    for i in range(mod-2):
        order.append(order[-1]*g%mod)
    where = [0]*mod
    for i,oi in enumerate(order):
        where[oi] = i

    nms = [0]*(mod-1)
    for i in map(int,ipt().split()):
        if i == 0:
            continue
        nms[where[i]] += 1

    ans = 0
    for i,ni in enumerate(nms):
        ans -= ni*order[(i*2)%(mod-1)]

    nn = multiply(nms*1,nms*1)


    for i in range(2*(mod-1)-1):
        ans += nn[i]*order[i%(mod-1)]

    print(ans//2)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
p=200003
n=int(input())
lst=list(map(int,input().split(" ")[:n]))
sume=0
for i in range(n):
    for j in range(i+1,n):
        modulo = ((lst[i]%p)*(lst[j]%p))%p
        sume+=modulo   
print(sume)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
B = list(map(int, input().split()))
tot = 0

A = []
for i in range(N):
  if B[i] != 0:
    A.append(B[i])
  
for i in range(len(A)):
    for j in range(len(A)-i-1):
        tot = tot + A[i]*A[i+j+1] % 200003

print(tot)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
tot = 0
    
for i in range(N):
    for j in range(N-i-1):
        tot = tot + A[i]*A[i+j+1] % 200003

print(tot)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 200_003
R = 2  # primitive root

ntt_mod = 998_244_353
ntt_root = 3
max_ntt = 20
roots, iroots = np.empty(1 << max_ntt,
                         np.int64), np.empty(1 << max_ntt, np.int64)

ntt_data = (ntt_mod, ntt_root, max_ntt, roots, iroots)
ntt_t = numba.typeof(ntt_data)


@njit((ntt_t, ), cache=True)
def ntt_precompute(ntt_data):
    MOD, root, max_ntt, roots, iroots = ntt_data

    def mpow(a, n):
        p = 1
        while n:
            if n & 1:
                p = p * a % MOD
            a = a * a % MOD
            n >>= 1
        return p

    roots[0] = iroots[0] = 1
    for n in range(max_ntt):
        x = mpow(root, (MOD - 1) >> n + 2)
        y = mpow(x, MOD - 2)
        for i in range(1 << n):
            roots[(1 << n) | i] = roots[i] * x % MOD
            iroots[(1 << n) | i] = iroots[i] * y % MOD
    return roots, iroots


@njit((ntt_t, i8[:], b1), cache=True)
def ntt(ntt_data, A, inverse):
    MOD, _, _, roots, iroots = ntt_data

    def mpow(a, n):
        p = 1
        while n:
            if n & 1:
                p = p * a % MOD
            a = a * a % MOD
            n >>= 1
        return p

    N = len(A)

    if not inverse:
        m = N >> 1
        while m:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m] * roots[k]
                    A[i], A[i + m] = x + y, x - y
            A %= MOD
            m >>= 1
    else:
        m = 1
        while m < N:
            for k in range(N // m >> 1):
                s = 2 * m * k
                for i in range(s, s + m):
                    x, y = A[i], A[i + m]
                    A[i], A[i + m] = x + y, (x - y) * iroots[k]
            A %= MOD
            m <<= 1
        for i in range(N):
            A[i] = A[i] * mpow(N, MOD - 2, MOD) % MOD
    return A


@njit((ntt_t, i8[:], i8[:]), cache=True)
def ntt_convolve(ntt_data, A, B):
    L = 1
    while 2 * L < len(A) + len(B) - 1:
        L *= 2
    L *= 2
    A = np.append(A, np.zeros(L - len(A), np.int64))
    B = np.append(B, np.zeros(L - len(B), np.int64))
    A = ntt(ntt_data, A, False)
    B = ntt(ntt_data, B, False)
    for i in range(len(A)):
        A[i] = A[i] * B[i] % ntt_data[0]
    return ntt(ntt_data, A, True)


ntt_precompute(ntt_data)

@njit((i8[:], ), cache=True)
def precompute(A):
    exp = np.zeros(MOD - 1, np.int64)
    log = np.zeros(MOD, np.int64)
    exp[0] = 1
    for k in range(1, MOD - 1):
        exp[k] = exp[k - 1] * R % MOD
        log[exp[k]] = k
    # r^k の個数を B[k] に入れる
    B = np.zeros(MOD - 1, np.int64)
    for x in A:
        if x != 0:
            B[log[x]] += 1
    return exp, log, B

@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def get_ans(A, C, exp, log):
    # 順序対について集計
    ans = 0
    for i in range(len(C)):
        x = exp[i % (MOD - 1)]
        ans += x * C[i]
    for a in A:
        x = a * a % MOD
        ans -= x
    return ans // 2

A = np.array(read().split(), np.int64)[1:]

exp, log, B = precompute(A)

B = np.append(B, [0] * ((1 << 19) - len(B)))
Bh, Bl = B >> 9, B & 511
x = ntt_convolve(ntt_data, Bh, Bh) << 18
x += ntt_convolve(ntt_data, Bh, Bl) << 10
x += ntt_convolve(ntt_data, Bl, Bl)

print(get_ans(A, x, exp, log))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
score=0
for i in range(N):
  for j in range(i+1,N):
    score+=(A[i]*A[j])%200003
print(score)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
j = 0
s = 0
for i in range (N - 1):
    i = 0
    j = j + 1
    for i in range (j):
        if not A[i] == 0 and not A[j] == 0:  
            s = s + (A[i] * A[j]) % 200003
        i = i + 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
b = 0
for i in input().split():
	if int(i)%200003 == 0:
		pass
	else:
		a.append(int(i))
		for j in range(len(a)-1):
			b += (a[-1]*a[j])%200003
			#print("a[-1],a[j]b",a[-1],a[j],b)
			#print("(a[-1]*a[j])%200003",(a[-1]*a[j])%200003)

print(b)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
B = []
for i in range(N):
    if A[i] != 0:
        B.append(A[i])
N = len(B)
P = 200003

d = {}
D = []
a = 1
for i in range(P-1):
    D.append(a)
    d[a] = i
    a *= 2
    a %= P

E = [0]*(P-1)
for i in range(P-1):
    if D[i]*2 > P:
        E[i] = 1

C = []
for i in range(N):
    C.append(d[B[i]])

c = len(C)
ANS = [0]*(P-1)
for i in range(c-1):
    for j in range(i+1,c):
        ANS[(C[i]+C[j]) % (P-1)] += 1

x = sum(D[i]*ANS[i] for i in range(P-1))
print(x)
# a = sum(B)
# b = sum(B[i]**2 for i in range(N))
# r = ((a**2-b)//2) % P

# print(P*x+r,C)