結果
問題 | No.1681 +-* |
ユーザー | kusirakusira |
提出日時 | 2024-03-04 23:29:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 218 ms / 2,000 ms |
コード長 | 23,068 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 138,508 KB |
最終ジャッジ日時 | 2024-09-29 17:34:39 |
合計ジャッジ時間 | 6,381 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 141 ms
82,432 KB |
testcase_01 | AC | 140 ms
82,100 KB |
testcase_02 | AC | 147 ms
82,540 KB |
testcase_03 | AC | 143 ms
82,104 KB |
testcase_04 | AC | 145 ms
82,432 KB |
testcase_05 | AC | 205 ms
138,328 KB |
testcase_06 | AC | 204 ms
137,840 KB |
testcase_07 | AC | 202 ms
138,508 KB |
testcase_08 | AC | 213 ms
134,956 KB |
testcase_09 | AC | 218 ms
134,448 KB |
testcase_10 | AC | 214 ms
134,440 KB |
testcase_11 | AC | 212 ms
134,952 KB |
testcase_12 | AC | 210 ms
134,444 KB |
testcase_13 | AC | 172 ms
107,628 KB |
testcase_14 | AC | 217 ms
134,172 KB |
testcase_15 | AC | 139 ms
82,364 KB |
testcase_16 | AC | 143 ms
82,536 KB |
testcase_17 | AC | 215 ms
134,448 KB |
testcase_18 | AC | 217 ms
134,704 KB |
testcase_19 | AC | 214 ms
134,576 KB |
ソースコード
# Python3/Pypy3テンプレート集#ライブラリ-------------------------------------------------------------------from bisect import *from heapq import *import collectionsfrom collections import dequefrom queue import Queuefrom itertools import groupbyimport itertoolsimport mathimport arrayimport stringimport copyfrom decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVENfrom functools import reducefrom functools import cmp_to_keyfrom operator import and_, or_, xor#便利スクリプト---------------------------------------------------------------INF = 8*10**9inf = 8*10**9mod = 998244353MOD = 10**9+7bigmod = 8128812800000059def YesNo(b): print("Yes") if b else print("No")def YESNO(b): print("YES") if b else print("NO")#標準入力---------------------------------------------------------------------import syssys.setrecursionlimit(10 ** 5 + 10000)input = sys.stdin.readline ####def int1(x): return int(x) - 1def II(): return int(input())def MI(): return map(int, input().split())def MI1(): return map(int1, input().split())def LI(): return list(map(int, input().split()))def LI1(): return list(map(int1, input().split()))def LIS(): return list(map(int, SI()))def LA(f): return list(map(f, input().split()))def LLI(rows_number): return [LI() for _ in range(rows_number)]def SI(): return input().strip('\n')def MS(): return input().split()def LS(): return list(input().strip('\n'))def LLS(rows_number): return [LS() for _ in range(rows_number)]def LMS(rows_number): return [MS() for _ in range(rows_number)]#関数------------------------------------------------------------------------###標準ライブラリ###def ceil(a,b): #切り捨てreturn (a+b-1)//bdef inv(a,p): #aのpを法とする逆元(aとpは互いに素)return pow(a,p-2,p)%pdef removeDuplicates_2D(A): #二次元配列の重複削除return list(map(list, set(map(tuple, A))))def cumulativeSum_1D(A): #配列Aの累積和return list(itertools.accumulate(A))def cumulativeSum_2D(S): #二次元配列Sの累積和 => 二次元リストh = len(S)w = len(S[0])CS = [[0 for _ in range(w)]for _ in range(h)]CCS = [[0 for _ in range(w)]for _ in range(h)]for i in range(h):for j in range(w):if(j==0):CS[i][0] = S[i][0]else:CS[i][j] = CS[i][j-1] + S[i][j]for i in range(h):for j in range(w):if(i==0):CCS[0][j] = CS[0][j]else:CCS[i][j] = CCS[i-1][j] + CS[i][j]return CCSdef string_to_runLength(S: str): #文字列/リストからラングレス圧縮grouped = groupby(S)res = []for k, v in grouped:res.append((k, int(len(list(v)))))return resdef runLength_to_string(L: "list[tuple]"): #ラングレス圧縮から文字列 => 文字だけres = ""for c, n in L:res += c * int(n)return resdef bfs(i,G): # i:始点n = len(G)dist = [-1] * npre = [-1] * nque = deque()dist[i] = 0que.append(i)while not len(que)==0:v = que.popleft()for next_v in G[v]:if dist[next_v] != -1:continuedist[next_v] = dist[v] + 1pre[next_v] = vque.append(next_v)return dist,predef bfs01(s, G): # i:始点 => distN = len(G)dist = [INF] * NS = deque([s])T = deque()dist[s] = 0d = 0while S:while S:v = S.popleft()for c, w in G[v]:if d+c < dist[w]:dist[w] = d+cif c:T.append(w)else:S.append(w)S, T = T, Sd += 1return distdef dijkstra(s,G): #s:始点 => cost,pre | G:タプルの中身(コスト,行先)n = len(G)hq = [(0, s)]heapify(hq)cost = [INF]*ncost[s]= 0pre = [-1] * nwhile hq:c,v = heappop(hq)if c > cost[v]:continuefor d,u in G[v]:tmp = d+cost[v]if tmp < cost[u]:cost[u] = tmppre[u] = vheappush(hq,(tmp,u))return cost, predef coordinates(A): # 変換表(元の値 : 座標圧縮の値),変換表2(座標圧縮の値: 元の値), 圧縮後配列B = sorted(set(A))C = { v: i for i, v in enumerate(B) }D = { i: v for i, v in enumerate(B) }E = list(map(lambda v: C[v], A))return C, D, Edef eng_L(): return list(string.ascii_lowercase)def ENG_L(): return list(string.ascii_uppercase)def bit_len(n): #bit長return n.bit_length()def bit_cnt(n): # bitにしたときの1の数cnt = 0for i in range(bit_len(n)+1):cnt += n>>i & 1return cntdef idx_le(A, x): # x 以下の最大の要素位置 / なければ "No"return bisect_right(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"def idx_lt(A, x): # x 未満の最大の要素位置 / なければ "No"return bisect_left(A, x)-1 if bisect_right(A, x)-1 != -1 else "No"def idx_ge(A, x): # x 以上の最小の要素位置 / なければ "No"return bisect_left(A, x) if bisect_left(A, x) != len(A) else "No"def idx_gt(A, x): # x 超過の最小の要素位置 / なければ "No"return bisect_right(A, x) if bisect_right(A, x) != len(A) else "No"def cnt_le(A, x): # x 以下の要素の個数if(idx_le(A, x) == "No"): return 0return idx_le(A, x) + 1def cnt_lt(A, x): # x 未満の要素の個数if(idx_lt(A, x) == "No"): return 0return idx_lt(A, x) + 1def cnt_ge(A, x): # x 以上の要素の個数return len(A) - cnt_lt(A, x)def cnt_gt(A, x): # x 超過の要素の個数return len(A) - cnt_le(A, x)###グリッドの操作###def transpose(A): #二次元配列の転置A_t = []for i in range(len(A[0])) :tmp = []for v in A :tmp.append(v[i])A_t.append(tmp)return A_tdef rotate_matrix(A): #グリッドを時計回りに90度回転return transpose(A[::-1])def convert(S,c): # グリッドをの 黒 マスの点集合に変換する | S: グリッド c:黒マスがなにか(ex "#",1)s = set()h = len(S)w = len(S[0])for i in range(h):for j in range(w):if S[i][j] == c:s.add((i, j))return sdef normalize(s): # グリッドの # マスの点集合を与えると最小の x 座標と最小の y 座標がともに 0 となるように平行移動して返すif(len(s)==0): return set()mi = min(i for (i, j) in s)mj = min(j for (i, j) in s)return set((i - mi, j - mj) for (i, j) in s)def up_shift(S): #グリッドの上シフトS = S[1:] + [S[0]]return Sdef down_shift(S): #グリッドの下シフトS = [S[-1]] + S[:-1]return Sdef left_shift(S): #グリッドの左シフトh = len(S)w = len(S[0])nS = [[0 for j in range(len(S[0]))]for i in range(len(S))]for i in range(h):for j in range(w):nS[i][j] = S[i][(j+1)%w]return nSdef right_shift(S): #グリッドの右シフトh = len(S)w = len(S[0])nS = [[0 for j in range(len(S[0]))]for i in range(len(S))]for i in range(h):for j in range(w):nS[i][j] = S[i][(j-1)%w]return nS###数学ライブラリ###def allAND(A): # 配列Aの総ANDreturn reduce(and_, A)def allOR(A): # 配列Aの総ORreturn reduce(or_, A)def allXOR(A): # 配列Aの総XORreturn reduce(xor, A)def allGCD(A): # 配列Aの総GCDif(len(A)==1):return A[0]g = math.gcd(A[0],A[1])for i in range(1,len(A)):g = math.gcd(g, A[i])return gdef mex(A): #配列Aのmexを求めるB = set()for a in A:if(a>=0):B.add(a)B = list(B)B.sort()if(len(B)==0):return 0if(B[0]!=0):return 0m = 0for i in range(1,len(B)):if(B[i]==B[i-1]+1):m +=1else:breakreturn m +1def gcd(a,b): #aとbの最大公約数を求めるreturn math.gcd(a,b)def lcm(a,b): #aとbの最小公倍数を求めるreturn a*b//gcd(a,b)def extgcd(a, b): # a,b =>ax+by=gcd(a,b)を満たす(g,x,y) a,bが互いに素のとき、xはaのbを法とする逆元if b:d, y, x = extgcd(b, a % b)y -= (a // b)*xreturn d, x, yreturn a, 1, 0def fact_L(n,mod): # [0!, 1! ..., n!] を返すfact = [1]p = 1for i in range(1,n+1):p *= ip %= modfact.append(p)return factdef bitCount_L(n): # n以下のそれぞれのbitカウントを返すbitcount = [0] * (n+1)for i in range(1,n+1):bitcount[i] = bitcount[i//2] + i%2return bitcountdef factorial(n, m=0): #nの階乗 | m:mod(デフォなし)if(n<0):return -1elif(n==0):return 1P = 1for i in range(1,n+1):P *= iif(m==0):continueP %= mreturn Pdef nPr(n, r, m=0): #順列nPrif(n<=0 or r<0 or n<r):return -1if(r==0):return 1P = 1for i in range(n,n-r,-1):P *= iif(m==0):continueP %= mreturn Pdef nCr(n, r): #組み合わせnCrif(n<r):return 0if(n==r):return 1if(n<=0 or r<0 or n<r):return -1N = 1for i in range(r):N *= n-iR = factorial(r)return N//Rdef nCrm(n,r,m=mod): #逆元を用いた組み合わせnCr%modif(n<r):return 0if(n==r):return 1if(n<=0 or r<0 or n<r):return -1over=1for i in range(n-r+1,n+1):over *= iover %= munder=1for i in range(1,r+1):under *= iunder %= mreturn over*pow(under,m-2,m)%mdef is_prime(n): #素数判定 => True/Falseif n == 2:return 1if n == 1 or n%2 == 0:return 0m = n - 1lsb = m & -ms = lsb.bit_length()-1d = m // lsbtest_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]for a in test_numbers:if a == n:continuex = pow(a,d,n)r = 0if x == 1:continuewhile x != m:x = pow(x,2,n)r += 1if x == 1 or r == s:return 0return 1def prime_L(n): #n以下の素数のリストis_prime = [True] * (n + 1)is_prime[0] = Falseis_prime[1] = Falsefor i in range(2, int(n**0.5) + 1):if not is_prime[i]:continuefor j in range(i * 2, n + 1, i):is_prime[j] = Falsereturn [i for i in range(n + 1) if is_prime[i]]def find_prime_factor(n):if n%2 == 0:return 2m = int(n**0.125)+1for c in range(1,n):f = lambda a: (pow(a,2,n)+c)%ny = 0g = q = r = 1k = 0while g == 1:x = ywhile k < 3*r//4:y = f(y)k += 1while k < r and g == 1:ys = yfor _ in range(min(m, r-k)):y = f(y)q = q*abs(x-y)%ng = math.gcd(q,n)k += mk = rr *= 2if g == n:g = 1y = yswhile g == 1:y = f(y)g = math.gcd(abs(x-y),n)if g == n:continueif is_prime(g):return gelif is_prime(n//g):return n//gelse:return find_prime_factor(g)def primeFactorization_2L(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストif(n<=10**6):arr = []temp = nfor i in range(2, int(-(-n**0.5//1))+1):if temp%i==0:cnt=0while temp%i==0:cnt+=1temp //= iarr.append([i, cnt])if temp!=1:arr.append([temp, 1])if arr==[]:arr.append([n, 1])return arrelse:res = {}while not is_prime(n) and n > 1:p = find_prime_factor(n)s = 0while n%p == 0:n //= ps += 1res[p] = sif n > 1:res[n] = 1R = []for r in res:R.append([r,res[r]])R.sort()return Rdef divisor_L(n): #nまでの約数のリストif(n==1):return [1]if(n<=10**6):lower_divisors , upper_divisors = [], []i = 1while i*i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]else:L = primeFactorization_2L(n)E = [[]for i in range(len(L))]for i in range(len(L)):for j in range(L[i][1]+1):E[i].append(L[i][0]**j)D = []for p in list(itertools.product(*E)):s = 1for v in p:s *= vD.append(s)D.sort()return Ddef floorsqrt(n): # N => ⌊√N⌋# only for n <= 10 ** 18ok = 10 ** 9 + 10ng = 0while ok - ng > 1:t = (ok + ng) // 2if t * t > n: ok = telse: ng = treturn ngdef decimal_to_nAry(d, n): #10進数からn進数へ変換する(n<=36) |int型 => str型if(d == 0): return "0"str_n = []while d:if d % n >= 10:str_n.append(chr(d%n+55))else:str_n.append(str(d%n))d //= nreturn "".join(str_n[::-1])def nAry_to_decimal(S, n): #n進数から10進数へ変換する(n<=36) | str型 => int型num = 0S = S.upper()S = list(S)for i in range(len(S)):if(("0"<=S[i]<="9")==False):S[i] = str(ord(S[i]) - 55)for i in range(1, len(S)+1):num += int(S[-i]) * pow(n, (i-1))return numdef roundOff(x,d): #四捨五入する x:対象の数字, d:四捨五入する位(正|負) => float型の数値return float(Decimal(x).quantize(Decimal(f"1E{d}"), rounding=ROUND_HALF_UP))###幾何ライブラリ###def dsin(d): #度数法でsinを計算するreturn math.sin(math.radians(d))def dcos(d): #度数法でcosを計算するreturn math.cos(math.radians(d))def rotate(x,y,d,cx=0,cy=0): #P(x,y)をA(cx,cy)を中心としてに反時計回りにd°回転 => [x,y]nx = (x-cx)*dcos(d)-(y-cy)*dsin(d)ny = (x-cx)*dsin(d)+(y-cy)*dcos(d)return [nx+cx,ny+cy]def findAngle(O,A,B): #∠AOBを求める(弧度法)s = [A[0]-O[0],A[1]-O[1]]t = [B[0]-O[0],B[1]-O[1]]u = s[0]*t[0]+s[1]*t[1]l = (s[0]**2+s[1]**2)**(1/2) * (t[0]**2+t[1]**2)**(1/2)v = u/lt = math.degrees(math.acos(v))return tdef outerProduct(Av,Bv): #二次元ベクトルの外積(=符号付面積)を求める(a×b)return Av[0]*Bv[1] - Bv[0]*Av[1]def CCW(O,A,B): #Oを中心として、Aから見たAとBの位置関係を求める。# -1: 時計回り, 0: 一直線上, 1: 反時計回りs = [A[0]-O[0],A[1]-O[1]]t = [B[0]-O[0],B[1]-O[1]]op = outerProduct(s,t)if(op > 0): return 1if(op < 0): return -1if(op == 0): return 0def matrixMultiplication_2D(a,b,m=mod): #行列の掛け算(a×b) m:modI,J,K,L = len(a),len(b[0]),len(b),len(a[0])if(L!=K):return -1c = [[0] * J for _ in range(I)]for i in range(I) :for j in range(J) :for k in range(K) :c[i][j] += a[i][k] * b[k][j]c[i][j] %= mreturn cdef matrixExponentiation_2D(x,n,m=mod): #行列の累乗 (x^n) m:mody = [[0] * len(x) for _ in range(len(x))]for i in range(len(x)):y[i][i] = 1while n > 0:if n & 1:y = matrixMultiplication_2D(x,y,m)x = matrixMultiplication_2D(x,x,m)n >>= 1return ydef twoCircles(A,B): #二つの円の半径の位置関係 | 引数はそれぞれ[x,y(=座標),r(=半径)]# 1 : 一方の円が他方の円を完全に含み、2 つの円は接していない# 2 : 一方の円が他方の円を完全に含み、2 つの円は接している# 3 : 2 つの円が互いに交差する# 4 : 2 つの円の内部に共通部分は存在しないが、2 つの円は接している# 5 : 2 つの円の内部に共通部分は存在せず、2 つの円は接していないx1 = A[0]x2 = B[0]y1 = A[1]y2 = B[1]r1 = A[2]r2 = B[2]d = abs((x1-x2)**2 + (y1-y2)**2)if(abs(r2-r1)**2>d):return 1elif(abs(r2-r1)**2==d):return 2elif((r1+r2)**2>d):return 3elif((r1+r2)**2==d):return 4elif((r1+r2)**2<d):return 5###デバッグ用ライブラリ###def TS(_str): #変数/リストに格納されている値を確認print('{}: {}'.format(_str, eval(_str)))def T2d(A): #二次元配列の確認用for a in A:print(*a)def T3d(A): #三次元配列の確認用for a in A:T2d(a)BR()def BR(): #横線で区切りを入れるprint("---")#クラス----------------------------------------------------------------------#カンニングペーパー-----------------------------------------------------------'''###標準ライブラリ###ceil(a,b): #切り捨てinv(a,p): #xのpを法とする逆元 | pは素数removeDuplicates_2D(A): #二次元配列の重複削除cumulativeSum_1D(A) #配列Aの累積和cumulativeSum_2D(S): #二次元配列Sの累積和 => 二次元リストstring_to_runLength(S: str) #文字列/リストからラングレス圧縮 => [(文字,個数), ...]の二次元リストrunLength_to_string(L: "list[tuple]") #ラングレス圧縮 => 文字列bfs(i,G) # i:始点 => dist,prebfs01(i,G) # i:始点 => distdijkstra(s,G): #s:始点 => cost,pre | G:タプルの中身(コスト,行先)coordinates(A) # 変換表(元の値 : 座標圧縮の値),変換表2(座標圧縮の値: 元の値), 圧縮後配列eng_L() #英小文字のリストENG_L() #英大文字のリストbit_len(n): #bit長bit_cnt(n): # bitにしたときの1の数idx_le(A, x) # x 以下の最大の要素位置 / なければ "No"idx_lt(A, x) # x 未満の最大の要素位置 / なければ "No"idx_ge(A, x) # x 以上の最小の要素位置 / なければ "No"idx_gt(A, x) # x 超過の最小の要素位置 / なければ "No"cnt_le(A, x) # x 以下の要素の個数cnt_lt(A, x) # x 未満の要素の個数cnt_ge(A, x) # x 以上の要素の個数cnt_gt(A, x) # x 超過の要素の個数###グリッドの操作###transpose(A): # 二次元配列の転置rotate_matrix(A): #グリッドを時計回りに90度回転convert(S, c): # グリッドをの 黒 マスの点集合に変換する | S: グリッド c:黒マスがなにか(ex "#",1)normalize(s): # グリッドの # マスの点集合を与えると最小の x 座標と最小の y 座標がともに 0 となるように平行移動して返すex) normalize(convert(S,c))up_shift(S): # グリッドの上シフトdown_shift(S): # グリッドの下シフトleft_shift(S): # グリッドの左シフトright_shift(S): # グリッドの右シフト###数学ライブラリ###allAND(A): # 配列Aの総ANDallOR(A): # 配列Aの総ORallXOR(A): # 配列Aの総XORallGCD(A): # 配列Aの総GCDmex(A) #配列Aのmexを求めるgcd(a,b) #aとbの最大公約数を求めるlcm(a,b) #aとbの最小公倍数を求めるextgcd(a, b): # a,b =>ax+by=gcd(a,b)を満たす(g,x,y) a,bが互いに素のとき、xはaのbを法とする逆元fact_L(n,mod): # [0!, 1! ..., n!] を返すbitCount_L(n): # n以下のそれぞれのbitカウントを返すfactorial(n,m) #nの階乗 | m:mod(デフォなし)nPr(n,r,m) #順列nPr | m:mod(デフォなし)nCr(n,r) #組み合わせ,nCrnCrm(n,r,m) #逆元を用いた組み合わせnCr%moddivisor_L(n) #nの約数のリストis_prime(n) #素数判定 => True/Falseprime_L(n) #nまでの素数のリストprimeFactorization_2L(n) #2以上の整数n => [[素因数, 指数], ...]の2次元リストfloorsqrt(n): # N => ⌊√N⌋decimal_to_nAry(num_10,n) #10進数からn進数へ変換する(n<=36) |int型 => str型nAry_to_decimal(num_n,n) #n進数から10進数へ変換する(n<=36) | str型 => int型roundOff(x,d): #四捨五入する x:対象の数字, d:四捨五入する位(正|負) => float型の数値###幾何ライブラリ###dsin(d): #度数法でsinを計算するdcos(d): #度数法でcosを計算するrotate(x,y,d,cx,cy): #P(x,y)をA(cx,cy)を中心としてに反時計回りにd°回転(デフォ原点) => [x,y]findAngle(O,A,B) #∠AOBを求める(弧度法) | 引数はそれぞれ[x,y(=座標)]outerProduct(Av,Bv) #二次元ベクトルの外積(=符号付面積)を求める(a×b) | 引数はそれぞれ[x,y(=座標)]CCW(O,A,B) #Oを中心として、Aから見たAとBの位置関係=> -1:時計回り, 0:一直線上, 1:反時計回り | 引数はそれぞれ[x,y(=座標)]matrixMultiplication_2D(a,b,m) #行列の掛け算(a×b) m:mod | 引数は二次元リストmatrixExponentiation_2D(x,n m) #行列の累乗 (x^n) m:mod | 引数は二次元リストtwoCircles(A,B): #二つの円の半径の位置関係 | 引数はそれぞれ[x,y(=座標),r(=半径)]=> 1, 2, 3, 4, 5 各数字に対応する位置関係の説明は上記参照###デバッグ用ライブラリ###TS(_str) # 変数/リストに格納されている値を確認 => 〇〇:××T2d(A): # 二次元配列の確認用T3d(A): # 三次元配列の確認用BR() # 横線で区切りを入れる###文法チートシート###|S|<x => "0"*(x-|S|) + S : str(n).zfill(x)全部大文字に変換:str.upper()全部小文字に変換:str.lower()先頭のみ大文字に変換:str.capitalize()各単語の先頭のみ大文字に変換(タイトルケース):str.title()大文字と小文字を入れ替える:str.swapcase()文字 → ASCIIコード ord(s)ASCIIコード → 文字 chr(x)ASCII表a65:A ~ 90:Z97:a ~ 122:z###おまけ###le: 以下lt: 未満ge: 以上gt: 超過'''#PyPyで再帰関数を用いる場合はコメントを外す----------------------------------# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')#----------------------------------------------------------------------------n = II()A = LI()B = []b = 1for i in range(n):b *= A[i]b %= MODB.append(b)p = 1P = [0,1]for i in range(n-1):p *= 3p %= MODP.append(p)P = P[::-1]# print(B)# print(P)ans = 0for i in range(n):ans += B[i]*(P[i]-P[i+1])ans %= MODprint(ans)