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:
n=int(input())
l=[int(x) for x in input().split()]
p=200003
w=[]
for i in range(n-1):
  for j in range(0,n):
    x=l[i]*l[j]
    d=x%p
    w.append(d)
print(sum(w))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[int(x) for x in input().split()]
p=200003
w=[]
for i in range(n-1):
  for j in range(i+1,n):
    x=l[i]*l[j]
    w.append(x)
g=sum(w)
print(g%p)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[int(x) for x in input().split()]
p=200003
w=[]
for i in range(n-1):
  for j in range(0,n):
    x=l[i]*l[j]
    w.append(x)
g=sum(w)
print(g%p)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
P=200003
a=[int(i) for i in input().split()]
b=[0 for i in range(P)]
for i in range(N):
    b[a[i]]+=1
M=1<<19
c=np.zeros(M)
for i in range(P-1):
    c[i]=b[pow(2,i,P)]
X=[int(i) for i in np.real(np.fft.ifft(np.fft.fft(c)*np.fft.fft(c)))]
ans=0
for k in range(M):
    ans+=X[k]*pow(2,k,P)
for i in range(N):
    ans-=(a[i]*a[i])%P
print(ans//2)

Submission status: Wrong Answer

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

p = 200003
N = int(input())
A = list(map(int,input().split()))
a = np.zeros(2*p)

g = 1
d = {}
p2 = [1]*p
for i in range(p):
    d[g] = i
    p2[i] = g
    g *= 2
    g %= p

for i in range(N):
    if A[i]==0:
        continue
    a[d[A[i]]] += 1

b = rfft(a)
b = irfft(b*b)
b = np.rint(b).astype(np.int64)

ans = 0
for i in range(p):
    ans += (b[i]+b[i+p-1])*p2[i]

for i in range(N):
    ans -= A[i]**2%p
ans //= 2
print(ans)

Submission status: Wrong Answer

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

p = 200003
N = int(input())
A = list(map(int,input().split()))
a = np.zeros(2*p)

g = 1
d = {}
p2 = [1]*p
for i in range(p):
    d[g] = i
    p2[i] = g
    g *= 2
    g %= p

for i in range(N):
    if A[i]==0:
        continue
    a[d[A[i]]] += 1

b = rfft(a)
b = irfft(b*b)
b = [int(x+0.5) for x in b]

ans = 0
for i in range(p):
    ans += (b[i]+b[i+p-1])*p2[i]

for i in range(N):
    ans -= A[i]**2%p
ans //= 2
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50


def run():
    N, *A = map(int, read().split())
    M = 200003
    P = [0] * (M-1)
    A = [a for a in A if a != 0]
    val2arr = {}
    arr2val = {}
    val = 1
    for p in range(M-1):
        val2arr[val] = p
        arr2val[p] = val
        val *= 2
        val %= M

    for a in A:
        k = val2arr[a]
        P[k] += 1

    L = 1 << (2 * M - 3).bit_length()

    fft_f = np.fft.ifft(np.fft.fft(P, L) ** 2)
    fft_f = [int(val.real) for val in fft_f]
    sum = 0
    for i in range(L):
        k = i % (M-1)
        sum += fft_f[i] * arr2val[k]

    sub = 0
    for a in A:
        sub += (a * a) % M
    print(int((sum - sub) // 2))



if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal

INF = 1 << 50


def run():
    N, *A = map(int, read().split())
    M = 200003
    P = [0] * (M-1)
    A = [a for a in A if a != 0]
    val2arr = {}
    arr2val = {}
    val = 1
    for p in range(M-1):
        val2arr[val] = p
        arr2val[p] = val
        val *= 2
        val %= M


    for a in A:
        k = val2arr[a]
        P[k] += 1

    L = 1 << (2 * M - 3).bit_length()

    fft_f = np.fft.ifft(np.fft.fft(P, L) ** 2)

    sum = 0
    for i in range(L):
        k = i % (M-1)
        sum += fft_f[i].real * arr2val[k]

    sub = 0
    for a in A:

        sub += (a * a) % M
    print(int(sum - sub) // 2)



if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from numpy.fft import rfft, irfft

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 200003
    P=mod

    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    cur=1
    base=2
    atoi=[0]*P
    itoa=[0]*(P-1)
    cnt=[0]*(P-1)
    for i in range(0,P-1):
        atoi[cur]=i
        itoa[i]=cur
        cur=cur*base%mod

    ta2=0
    for a in A:
        if a==0:
            continue
        i=atoi[a]
        cnt[i]+=1
        ta2+=a*a%P
    rf=rfft(cnt, 2*(P-1))
    X = irfft(rf * rf)
    #printe(X,sum(X))
    ans=0
    for i in range(P-1):
        ans+=itoa[i]*(X[i]+X[P-1+i])

    ans=round(ans)
    print(int((ans-ta2)//2+0.5))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy 
 
def convolve(g, h):
  s=len(g)+len(h)+1
  n=1
  while n<s:
    n*=2
  gg=numpy.fft.fft(g+[0]*(n-len(g)))
  hh=numpy.fft.fft(h+[0]*(n-len(h)))
  ff=[gg[i]*hh[i] for i in range(n)]
  ff=numpy.fft.ifft(ff)
  ans=[int(ff[i].real+0.5) for i in range(n)]
  return ans

p=200003
n=int(input())
arr=list(map(int,input().split()))
pos={}
tmp=1
for i in range(p):
  pos[tmp]=i
  tmp*=2
  tmp%=p
cnt1=[0]*p
cnt2=[0]*p
coef=[0]*p
for val in arr:
  if val!=0:
    cnt1[pos[val]]+=1
    cnt2[pos[val]]+=1
    coef[pos[(val*val)%p]]-=1
ans=convolve(cnt1,cnt2)
total=0
for i in range(len(ans)):
  if ans[i]!=0:
    total+=(ans[i]//2)*pow(2,i,p)
print(total)

Submission status: Wrong Answer

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

@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)
fft, ifft = np.fft.fft, np.fft.ifft
fft_len = 210_000
FB = fft(B, fft_len)
C = np.rint(ifft(FB * FB, fft_len)).astype(np.int64)

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

Submission status: Wrong Answer

Solution code:
import scipy.fftpack as F
from numpy import *
m=200003
n=int(input())
a=[0]*m
b=[0]*m
ans=0
for i in range(m-1):
    a[pow(2,i,m)]=i
for i in map(int,input().split()):
    if i:
        b[a[i]]+=1
        ans-=i*i%m
b=array(b,dtype=float64)
b=F.fft(b)
b=b*b
b=F.ifft(b)
for i,j in enumerate(b):
    ans+=int(round(j.real))*pow(2,i,m)
print(ans//2)

Submission status: Wrong Answer

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

print(tot)

Submission status: Wrong Answer

Solution code:
import numpy as np
#fft = np.fft.fft
#ifft = np.fft.ifft
from scipy.fftpack import fft, ifft

(N, ) = [int(n) for n in input().split()]
A = [int(n) for n in input().split()]

P = 200003
#P = 13

log = [0 for _ in range(P)] # log2x (1 <= x <= P-1)
exp = [0 for _ in range(P)] # 2^x (1 <= x <= P-1)

base = 2

a = 1
for i in range(P):
    if i != 0:
        #print("log {} = {}, exp {} = {}".format(a, i, i, a))
        exp[i] = a
        log[a] = i
    a *= base
    a %= P

c = [0 for _ in range(P)]
for a in A:
    c[a] += 1

d = [c[exp[i]] for i in range(P)]

d = np.array(d[1:], dtype=np.float64)
D = fft(d)
D = D ** 2
dd = ifft(D)
    
ans = 0
for k in range(P-1):
    ans += dd[(k-1+P-1)%(P-1)] * exp[k+1]

ans = int(round(abs(ans)))

for a in A:
    ans -= (a * a) % P

print(ans // 2)

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.fftpack as fft

mod = 200003
n = int(input())
a = []
for i in map(int, input().split()):
    if i % mod == 0:
        n -= 1
    else:
        a.append(i % mod)

tab = [0] * mod
j = 1
for i in range(mod-2):
    tab[j] = i
    j = (j*2) % mod

b = [0] * (mod-1)
for i in a:
    b[tab[i]] += 1

b = np.array(b, dtype=np.float64)
b = fft.fft(b)
b = b*b
b = fft.ifft(b)

ans = 0
for i, j in enumerate(b):
    ans += int(round(j.real))*pow(2, i, mod)

for i in a:
    ans -= i*i % mod
print(ans//2)

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.fftpack as fft

mod = 200003
n = int(input())
a = []
for i in map(int, input().split()):
    if i % mod == 0:
        n -= 1
    else:
        a.append(i % mod)

tab = [0] * mod
j = 1
for i in range(mod-2):
    tab[j] = i
    j = (j*2) % mod

b = [0] * (mod-1)
for i in a:
    b[tab[i]%(mod-1)] += 1

b = np.array(b, dtype=np.float64)
b = fft.fft(b)
b = b*b
b = fft.ifft(b)

ans = 0
for i, j in enumerate(b):
    ans += int(round(j.real))*pow(2, i, mod)

for i in a:
    ans -= i*i % mod
print(round(ans/2))

Submission status: Wrong Answer

Solution code:
# フーリエ変換は、多項式の積動詞の積において指数の和が一定となるようなものをまとめる感じ
# Ci=Aj*Bk となるときはi=j+kのものをまとめている
# 今回はmod=200003でi+jが一致するものを集めたいので
# 係数→log→フーリエ変換→指数で戻す、という流れ？
import numpy as np
import sys

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

mod = 200003
n = int(readline())
A = list(map(int, input().split()))
F = np.zeros(mod, dtype=int)
prime = 2
now = 1
pow2 = [0] * (mod)
log2 = [-1] * (mod)
# 累乗の関数と逆関数を求めておく。
for i in range(mod):
    pow2[i] = now
    log2[pow2[i]] = i
    now *= prime
    now %= mod

# 今度は2019*2020をうまく表すにはlogを取ってから累乗の係数に落とせばよい。
for i in range(n):
    if A[i]:
        pos = log2[A[i]]
        F[pos] += 1


# maspyさんのyukicoder解答から
def fft_convolve(f, g, mod=mod):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    fft = np.fft.rfft
    ifft = np.fft.irfft
    Lf = len(f)
    Lg = len(g)
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1
    fh = f >> 15
    gl = g & (1 << 15) - 1
    gh = g >> 15
    conv = lambda f, g: ifft(fft(f, fft_len) * fft(g, fft_len))[:L]
    x = conv(fl, gl) % mod
    y = conv(fl + fh, gl + gh) % mod
    z = conv(fh, gh) % mod
    a, b, c = map(lambda x: (x + 0.5).astype(np.int64), [x, y, z])
    return (a + ((b - a - c) << 15) + (c << 30)) % mod


x = fft_convolve(F, F, mod)
# for i in range(len(x)):
# if x[i]:
#     print(i, i % mod, x[i])
ans1 = 0
L = len(x)
for i in range(L):
    ans1 += pow2[i % (mod - 1)] * x[i]  # why mod-1????????
for i in range(n):
    ans1 -= A[i] * A[i] % mod
print(ans1 // 2)

# ans2 = 0
# for i in range(n):
#     for j in range(i + 1, n):
#         ans2 += A[i] * A[j] % mod
#         print((i, j), A[i] * A[j] % mod)
#         print(log2[A[i] * A[j] % mod])
# print(ans2)

Submission status: Wrong Answer

Solution code:
# フーリエ変換は、多項式の積動詞の積において指数の和が一定となるようなものをまとめる感じ
# Ci=Aj*Bk となるときはi=j+kのものをまとめている
# 今回はmod=200003でi+jが一致するものを集めたいので
# 係数→log→フーリエ変換→指数で戻す、という流れ？
import numpy as np
import sys

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

mod = 200003
n = int(readline())
A = list(map(int, input().split()))
F = np.zeros(mod, dtype=int)
prime = 2
now = 1
pow2 = [0] * (mod)
log2 = [-1] * (mod)
# 累乗の関数と逆関数を求めておく。
for i in range(mod):
    pow2[i] = now
    log2[pow2[i]] = i
    now *= prime
    now %= mod

# 今度は2019*2020をうまく表すにはlogを取ってから累乗の係数に落とせばよい。
for i in range(n):
    if A[i]:
        pos = log2[A[i]]
        F[pos] += 1


# maspyさんのyukicoder解答から
def fft_convolve(f, g, mod=mod):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    fft = np.fft.rfft
    ifft = np.fft.irfft
    Lf = len(f)
    Lg = len(g)
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1
    fh = f >> 15
    gl = g & (1 << 15) - 1
    gh = g >> 15
    conv = lambda f, g: ifft(fft(f, fft_len) * fft(g, fft_len))[:L]
    x = conv(fl, gl) % mod
    y = conv(fl + fh, gl + gh) % mod
    z = conv(fh, gh) % mod
    a, b, c = map(lambda x: (x + 0.5).astype(np.int64), [x, y, z])
    return (a + ((b - a - c) << 15) + (c << 30)) % mod


x = fft_convolve(F, F, mod)
# for i in range(len(x)):
# if x[i]:
#     print(i, i % mod, x[i])
ans1 = 0
L = len(x)
x[0 : L - (mod - 1)] += x[mod - 1 : L]
x = x[: mod - 1]
for i in range(len(x)):
    ans1 += pow2[i % (mod - 1)] * x[i]  # why mod-1????????
for i in range(n):
    ans1 -= A[i] * A[i] % mod
print(ans1 // 2)

# ans2 = 0
# for i in range(n):
#     for j in range(i + 1, n):
#         ans2 += A[i] * A[j] % mod
#         print((i, j), A[i] * A[j] % mod)
#         print(log2[A[i] * A[j] % mod])
# print(ans2)

Submission status: Wrong Answer

Solution code:
# フーリエ変換は、多項式の積動詞の積において指数の和が一定となるようなものをまとめる感じ
# Ci=Aj*Bk となるときはi=j+kのものをまとめている
# 今回はmod=200003でi+jが一致するものを集めたいので
# 係数→log→フーリエ変換→指数で戻す、という流れ？
import numpy as np
import sys

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

mod = 200003
n = int(readline())
A = list(map(int, input().split()))
F = np.zeros(mod, dtype=int)
prime = 2
now = 1
pow2 = [0] * (mod)
log2 = [-1] * (mod)
# 累乗の関数と逆関数を求めておく。
for i in range(mod):
    pow2[i] = now
    log2[pow2[i]] = i
    now *= prime
    now %= mod

# 今度は2019*2020をうまく表すにはlogを取ってから累乗の係数に落とせばよい。
for i in range(n):
    if A[i]:
        pos = log2[A[i]]
        F[pos] += 1


# maspyさんのyukicoder解答から
def fft_convolve(f, g, mod=mod):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    fft = np.fft.rfft
    ifft = np.fft.irfft
    Lf = len(f)
    Lg = len(g)
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1
    fh = f >> 15
    gl = g & (1 << 15) - 1
    gh = g >> 15
    conv = lambda f, g: ifft(fft(f, fft_len) * fft(g, fft_len))[:L]
    x = conv(fl, gl) % mod
    y = conv(fl + fh, gl + gh) % mod
    z = conv(fh, gh) % mod
    a, b, c = map(lambda x: (x + 0.5).astype(np.int64), [x, y, z])
    return (a + ((b - a - c) << 15) + (c << 30)) % mod


x = fft_convolve(F, F, mod)
# for i in range(len(x)):
# if x[i]:
#     print(i, i % mod, x[i])
ans1 = 0

for i in range(len(x)):
    ans1 += pow2[i % (mod - 1)] * x[i]  # why mod-1????????
for i in range(n):
    ans1 -= A[i] * A[i] % mod
print(ans1 // 2)

# ans2 = 0
# for i in range(n):
#     for j in range(i + 1, n):
#         ans2 += A[i] * A[j] % mod
#         print((i, j), A[i] * A[j] % mod)
#         print(log2[A[i] * A[j] % mod])
# print(ans2)

Submission status: Wrong Answer

Solution code:
# フーリエ変換は、係数のidxの和が一定となるようなものをまとめる感じ
# Ci=AjBk となるときはi=j+kのものをまとめている(mod pで)
# 今回はmod=200003でi+jが一致するものを集めたいので
# 最初に与えられた数を指数に変換しないといけない
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)

mod = 200003
n = int(readline())
A = list(map(int, input().split()))
F = np.zeros(mod, dtype=int)
prime = 2
now = 1
pow2 = [0] * (mod)
log2 = [-1] * (mod)
# 累乗の関数と逆関数を求めておく。
for i in range(mod):
    pow2[i] = now
    log2[pow2[i]] = i
    now *= prime
    now %= mod

# 今度は2019*2020をうまく表すにはlogを取ってから累乗の係数に落とせばよい。
for i in range(n):
    if A[i]:
        pos = log2[A[i]]
        F[pos] += 1


fft_len = 1 << 20

# maspyさんのyukicoder解答から
def fft_convolve(f, g, mod=mod):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    fft = np.fft.rfft
    ifft = np.fft.irfft
    Lf = len(f)
    Lg = len(g)
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1
    fh = f >> 15
    gl = g & (1 << 15) - 1
    gh = g >> 15
    conv = lambda f, g: ifft(fft(f, fft_len) * fft(g, fft_len))[:L]
    x = conv(fl, gl) % mod
    y = conv(fl + fh, gl + gh) % mod
    z = conv(fh, gh) % mod
    a, b, c = map(lambda x: (x + 0.5).astype(np.int64), [x, y, z])
    return (a + ((b - a - c) << 15) + (c << 30)) % mod


x = fft_convolve(F, F, mod)
# for i in range(len(x)):
# if x[i]:
#     print(i, i % mod, x[i])
ans1 = 0

for i in range(1, 2 * mod - 1):
    ans1 += pow2[i % (mod - 1)] * x[i]  # why mod-1????????
for i in range(n):
    ans1 -= A[i] * A[i] % mod
print(ans1 // 2)

# ans2 = 0
# for i in range(n):
#     for j in range(i + 1, n):
#         ans2 += A[i] * A[j] % mod
#         print((i, j), A[i] * A[j] % mod)
#         print(log2[A[i] * A[j] % mod])
# print(ans2)

Submission status: Wrong Answer

Solution code:

n = int(input())
xs = [int(x) for x in input().split(' ')]

cur_sum = sum(xs)

MOD = 200003

ans, cnt = 0, 0

for i in range(len(xs)):
    cur_sum -= xs[i]
    term = xs[i] * cur_sum
    cnt += term // MOD
    ans += term

cur = ans // MOD
print(ans % MOD + (MOD * (cur - cnt + 1)))

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.fftpack as fft

mod = 200003
n = int(input())
a = []
for i in map(int, input().split()):
    if i % mod == 0:
        n -= 1
    else:
        a.append(i % mod)

tab = [0] * mod
j = 1
for i in range(mod-2):
    tab[j] = i
    j = (j*2) % mod

b = [0] * (mod-1)
for i in a:
    b[tab[i]%(mod-1)] += 1

b = np.array(b, dtype=np.float128)
b = fft.fft(b)
b = b*b
b = fft.ifft(b)

ans = 0
for i, j in enumerate(b):
    ans += int(round(j.real))*pow(2, i, mod)

for i in a:
    ans -= i*i % mod
print(ans//2)

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.fftpack as fft

mod = 200003
n = int(input())
a = []
for i in map(int, input().split()):
    if i % mod == 0:
        n -= 1
    else:
        a.append(i % mod)

tab = [0] * mod
j = 1
for i in range(mod-2):
    tab[j] = i
    j = (j*2) % mod

b = [0] * (mod-1)
for i in a:
    b[tab[i]%(mod-1)] += 1

b = np.array(b, dtype=np.float64)
b = fft.fft(b)
b = b*b
b = fft.ifft(b)

ans = 0
for i, j in enumerate(b):
    ans += int(round(j.real))*pow(2, i, mod)

for i in a:
    ans -= i*i % mod
print(ans//2)

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.fftpack as fft

mod = 200003
n = int(input())
a = []
for i in map(int, input().split()):
    if i % mod == 0:
        n -= 1
    else:
        a.append(i % mod)

tab = [0] * mod
j = 1
for i in range(mod-2):
    tab[j] = i
    j = (j*2) % mod

b = [0] * (mod*2)
for i in a:
    b[tab[i]] += 1

b = np.array(b, dtype=np.float32)
b = fft.fft(b)
b = b*b
b = fft.ifft(b)

ans = 0
for i, j in enumerate(b):
    ans += int(round(j.real))*pow(2, i, mod)

for i in a:
    ans -= i*i % mod
print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

def fft_convolve(f, g):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    fft = np.fft.rfft
    ifft = np.fft.irfft
    Lf = len(f)
    Lg = len(g)
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1
    fh = f >> 15
    gl = g & (1 << 15) - 1
    gh = g >> 15

    def conv(f, g):
        return ifft(fft(f, fft_len) * fft(g, fft_len))[:L]

    x = conv(fl, gl)
    y = conv(fl + fh, gl + gh)
    z = conv(fh, gh)
    a, b, c = map(lambda x: (x + .5).astype(np.int64), [x, y, z])
    return (a + ((b - a - c) << 15) + (c << 30))


ROOT=2
P=200003
pw=[1]*(P-1)
lg=[-1]*P

for i in range(1,len(pw)):
    pw[i]=ROOT*pw[i-1]%P
for i in range(len(pw)):
    lg[pw[i]]=i

N=int(input())
A=np.array([int(x) for x in input().split()],dtype=np.int64)
B=[0]*P
for a in A:
    if a==0:
        continue
    B[lg[a]]+=1
B=np.array(B,dtype=np.int64)
C=fft_convolve(B,B)
ans=0
for a in A:
    ans-=a*a%(P-1)
for i in range(len(C)):
    ans+=C[i]*pw[i%(P-1)]
ans//=2
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
mod=200003
sm2=0
sm=0
for i in a:
  sm2 += i**2
  sm2 %= mod
  sm += i
  sm %= mod

print(((sm**2)%mod-sm2)*100002%mod)

Submission status: Wrong Answer

Solution code:
for i in range(10):
    print("<",i+3,0,i+4)
    print("+",i+3,i+4,i+4)
for j in range(10):
    print("<",i+14,0,i+15)
    print("+",i+14,i+15,i+15)

for i in range(10):
    print("<",i+3,i+4,i+25)
    print("<",i+14,i+15,i+35)

for i in range(10):
    print("<",i+35,25,i+45)

for i in range(10):
    for j in range(10):
        print("<",j+45,i+25,45)
        print("+",2,45,2)

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]%mod)*(dp[i+1]%mod))+mod)%mod
    cache+=(((arr[i])*(dp[i+1])))//mod
print(ans+(cache*mod)%mod+mod)

'''
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)%mod
cache+=ans//mod
print(ans+mod*cache)

'''
474287
'''

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
p = 200003
SA = sum(A)

T = [0]*p
ST = [0]*p
for i in range(N):
    T[A[i]]+=1
ST[p-1]=T[p-1]
for i in range(p-1):
    ST[p-2-i]=T[p-2-i]+ST[p-1-i]
ST.append(0)
OVER = [0]*p
l = 2
r = int(p/l)+1
while l<p:
    if r<=l:
        r=l+1
    OVER[l] = T[l]*ST[r]
    l+=1
    r = int(p/l)+1

A.sort()
out = 0
for i in range(N):
    tmp = 0
    if A[i]!=0:
        SA = SA - A[i]
        out += SA*A[i]%p+max(0,(OVER[A[i]]-1))*p
print(out)