結果

問題 No.2494 Sum within Components
ユーザー mattu34
提出日時 2023-10-07 16:25:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 500 ms / 2,000 ms
コード長 2,967 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 127,584 KB
最終ジャッジ日時 2024-07-26 17:51:00
合計ジャッジ時間 5,807 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import *
from fractions import Fraction
import heapq
import bisect
import itertools
def compress(arr):
    (*XS,) = set(arr)
    XS.sort()
    return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)}
def ctov(c):
    return ord(c) - ord("a")
def CTOV(c):
    return ord(c) - ord("A")
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def convert_90(matrix):
    # 入力行列の行数と列数を取得
    rows = len(matrix)
    cols = len(matrix[0])
    # 90度回転後の行列を初期化
    rotated_matrix = [[0] * rows for _ in range(cols)]
    # 元の行列を90度回転させて新しい行列に格納
    for i in range(rows):
        for j in range(cols):
            rotated_matrix[j][rows - 1 - i] = matrix[i][j]
    return rotated_matrix
def cropping(MAP, mark):
    M_y, M_x = 0, 0
    m_y, m_x = INF, INF
    H, W = len(MAP), len(MAP[0])
    for i in range(H):
        for j in range(W):
            if MAP[i][j] == mark:
                M_y = max(i, M_y)
                M_x = max(M_x, j)
                m_y = min(i, m_y)
                m_x = min(m_x, j)
    new = [[0] * (M_x - m_x + 1) for _ in range(M_y - m_y + 1)]
    for i in range(m_y, M_y + 1):
        for j in range(m_x, M_x + 1):
            new[i - m_y][j - m_x] = MAP[i][j]
    return new
# ダブリング dp[i][j]:=jから2**i回遷移したときの到達点
# https://atcoder.jp/contests/abc167/submissions/40815296
# N,K=map(int,input().split())
# A=list(map(int,input().split()))
# dp=[[-1]*N for _ in range(60)]
# for j in range(N):
#     dp[0][j]=A[j]-1
# for i in range(1,60):
#     for j in range(N):
#         dp[i][j]=dp[i-1][dp[i-1][j]]
# i=0
# now=0
# while(K>0):
#     if (K&1)==1:
#         now=dp[i][now]
#     i+=1
#     K>>=1
# print(now+1)
dxdy1 = ((0, 1), (0, -1), (1, 0), (-1, 0))
dxdy2 = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1))
dxdy3 = ((0, 1), (1, 0))
dxdy4 = ((1, 1), (1, -1), (-1, 1), (-1, -1))
INF = float("inf")
MOD = 998244353
mod = 998244353
# memo : len([a,b,...,z])==26
N, M = map(int, input().split())
A = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)
ans = 1
visited = [0] * N
for i in range(N):
    if visited[i] == 1:
        continue
    tmp = 0
    cnt = 0
    q = deque()
    q.append(i)
    while q:
        node = q.pop()
        visited[node] = 1
        tmp += A[node]
        cnt += 1
        for nxt in adj[node]:
            if visited[nxt] == 1:
                continue
            visited[nxt] = 1
            q.append(nxt)
    ans *= pow(tmp, cnt, MOD)
    ans %= MOD
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0