結果
| 問題 | No.2494 Sum within Components |
| ユーザー |
 Asahi
|
| 提出日時 | 2023-10-06 22:10:20 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 593 ms / 2,000 ms |
| コード長 | 20,081 bytes |
| コンパイル時間 | 3,492 ms |
| コンパイル使用メモリ | 98,640 KB |
| 実行使用メモリ | 99,916 KB |
| 最終ジャッジ日時 | 2024-07-26 16:16:11 |
| 合計ジャッジ時間 | 8,474 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
import java.util.*;import java.io.*;import java.sql.Array;import java.util.stream.*;import java.util.function.*;class Main implements Runnable{void solve(){int N = in.nextInt() , M = in.nextInt();long [] A = in.LongArray(N);UnionFind uf = new UnionFind(N);for(int i = 0 ; i < M ; i ++ ){int u = in.nextInt() , v = in.nextInt();--u;--v;uf.unite(u , v);}List<List<Integer>> g = uf.Groups();long ans = 1 ;for(int i = 0 ; i < g.size() ; i ++ ){long sum = 0 ;for(int v : g.get(i)) sum = ((sum + A[v])% MOD9);long tot = power(sum , g.get(i).size()) % MOD9;ans = (ans * tot) % MOD9;}out.print(ans % MOD9);}long power(long a, long b) {long res = 1;while (b > 0) {if ((b & 1) != 0) {res = (res * a) % MOD9;}a = (a * a) % MOD9;b >>= 1;}return res;}double dist_m(ip p1 , ip p2) { return Math.abs(p1.fi - p2.fi) + Math.abs(p1.se - p2.se) ; }double dist_u(ip p1 , ip p2) { return Math.sqrt(Math.pow(p1.fi - p2.fi , 2) + Math.pow(p1.se - p2.se, 2)); }public static void main(String[] args){new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();}public void run(){solve();out.flush();}record ip(int fi , int se) { public String toString() { return fi +" "+ se ;} }record lp(long fi , long se) { public String toString() { return fi +" "+ se ;} }public double dist(lp p1 , lp p2) { return Math.sqrt((p1.fi - p2.fi) * (p1.fi - p2.fi) + (p1.se - p2.se) * (p1.se - p2.se)); }public int max(int ... a) { int max = -1 ; for(int p : a) max = Math.max(max , p); return max; }public int min(int ... a) { int min = Integer.MAX_VALUE ; for(int p : a) min = Math.min(min , p); return min; }public long max(long ... a) { long max = -1 ; for(long p : a) max = Math.max(max , p); return max; }public long min(long ... a) { long min = Long.MAX_VALUE ; for(long p : a) min = Math.min(min , p); return min; }public int sum(int ... a) { int sum = 0 ; for(int p : a) sum += p ; return sum ;}public long sum(long ... a) { long sum = 0 ; for(long p : a) sum += p ; return sum ;}public int abs(int a , int b) { return (int) Math.abs(a - b) ; }public long abs(long a , long b) { return (long) Math.abs(a - b) ; }public int pow(int a , int b) { return (int) Math.pow(a , b) ; }public long pow(long a , long b) { return (long) Math.pow(a , b) ; }public long rec(long a) { return a == 1 ? 1 : a * rec(a - 1); }public long [] recmod(int a , long MOD) { long [] recMod = new long[1 << 17] ; recMod[1] = 1 ; for(int i = 2 ; i < (1 << 17) ; i ++ ) recMod[i] =(recMod[i - 1] * i) % MOD9; return recMod; }public int [] rev(int [] a) { int [] r = new int[a.length] ; int idx = a.length ; for(int p : a) r[--idx] = p ; return r ; }public long [] rev(long [] a) { long [] r = new long[a.length] ; int idx = a.length ; for(long p : a) r[--idx] = p ; return r ; }public int gcd(int a, int b) { return b == 0 ? a: gcd(b, a % b); }public int lcm(int a, int b) { return a / gcd(a, b) * b; }public long gcd(long a, long b) { return b == 0 ? a: gcd(b, a % b); }public long lcm(long a, long b) { return a / gcd(a, b) * b; }public int gcd(int ... a) { int gcd = 0 ; for(int p : a) gcd = gcd(gcd , p) ; return gcd ; }public long gcd(long ... a) { long gcd = 0L ; for(long p : a) gcd = gcd(gcd , p) ; return gcd ; }public int lcm(int ... a) { int lcm = 1 ; for(int p : a) lcm = lcm(lcm , p) ; return lcm ; }public long lcm(long ... a) { long lcm = 1 ; for(long p : a) lcm = lcm(lcm , p) ; return lcm ; }public char upper(char c) { return (char)('A' + (c - 'a')); }public char lower(char c) { return (char)('a' + (c - 'A')); }public String yn(boolean a) { return a ? yes : no ; }public String rev(String a) { return new StringBuilder(a).reverse().toString(); }public void fill(int [] a , int v) { Arrays.fill(a , v); }public void fill(long [] a , long v) { Arrays.fill(a , v); }public void fill(int [][] a , int v) { for(int [] aa : a) fill(aa , v) ; }public void fill(long [][] a , long v) { for(long [] aa : a) fill(aa , v) ; }public void fill(int [][][] a , int v) { for(int [][] aa : a) fill(aa , v); }public void fill(long [][][] a , long v) { for(long [][] aa : a) fill(aa , v); }public int [] copy(int [] a) { return Arrays.copyOf(a , a.length); }public long [] copy(long [] a) { return Arrays.copyOf(a , a.length); }public String bin(int a , int len) { String b = Integer.toBinaryString(a); while(b.length() < len) b = "0" + b ; return b ; }public void debug(int [] a) { out.println(Arrays.toString(a)); fl();}public void debug(long [] a) { out.println(Arrays.toString(a)); fl();}public void debug(double [] a) { out.println(Arrays.toString(a)); fl();}public void debug(String [] a) { out.println(Arrays.toString(a)); fl();}public void debug(char [] a) { out.println(Arrays.toString(a)); fl();}public void debug(boolean [] a) { char [] c = conv(a); debug(c); fl();}public void debug(int [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}public void debug(long [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}public void debug(double [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}public void debug(String [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}public void debug(char [][] a) { for(int i = 0 ; i < a.length ; i ++ ) out.println(Arrays.toString(a[i])); fl();}public void debug(boolean [][] a) { char [][] c = new char [a.length][a[0].length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = conv(a[i]) ;debug(c); fl();}private char [] conv(boolean [] a) { char [] c = new char[a.length] ; for(int i = 0 ; i < a.length ; i ++ ) c[i] = a[i] ? 'O' : 'X' ; return c ;}private void fl() { out.flush(); }PrintWriter out = new PrintWriter(System.out);In in = new In();static final long MOD7 = 1000000007;static final long MOD9 = 998244353;static final int inf = (1 << 30);static final long lnf = (1L << 60);final String yes = "Yes";final String no = "No" ;final char [] dir = {'U','R','D','L'};final int [] dy4 = {-1,0,1,0};final int [] dx4 = {0,1,0,-1};final int [] dy8 = {-1,-1,-1,0,1,1,1,0};final int [] dx8 = {-1,0,1,1,1,0,-1,-1};}class LazySegmentTree {final long[] Dat;final long[] Laz;final int N;final long E0;final long E1;final LongBinaryOperator F;final LongBinaryOperator G;final LongBinaryOperator H;final LongBinaryOperator P;final int[] Stack = new int[64];//初期配列 , dat(関与しない値) , lazy(関与しない値) , dat() , dat&lazy() , lazy() , lazy*len()public LazySegmentTree(int n, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p) {this.E0 = e0;this.E1 = e1;this.F = f; this.G = g; this.H = h; this.P = p;int k = 1;while (k <= n) k <<= 1;this.Dat = new long[k << 1];this.Laz = new long[k << 1];this.N = k;Arrays.fill(Dat, E0);Arrays.fill(Laz, E1);}public LazySegmentTree(long[] src, long e0, long e1, LongBinaryOperator f, LongBinaryOperator g, LongBinaryOperator h, LongBinaryOperator p) {this(src.length, e0, e1, f, g, h, p);build(src);}private void build(long[] src) {System.arraycopy(src, 0, Dat, N, src.length);for (int i = N - 1; i > 0; i--) Dat[i] = F.applyAsLong(Dat[i << 1 | 0], Dat[i << 1 | 1]);}public void update(int l, int r, long v) {if (l >= r) return;int m = updown(l, r);l += N; r += N;for (; l < r; l >>= 1, r >>= 1) {if ((l & 1) != 0) {Laz[l] = H.applyAsLong(Laz[l], v); l++;}if ((r & 1) != 0) {r--; Laz[r] = H.applyAsLong(Laz[r], v);}}for (int i = 0; i < m; i++) {int k = Stack[i];Dat[k] = F.applyAsLong(calcDat(k << 1 | 0), calcDat(k << 1 | 1));}}public long query(int i) {int k = 1;int l = 0, r = N;while (k < N) {int kl = k << 1 | 0;int kr = k << 1 | 1;Dat[k] = F.applyAsLong(calcDat(kl), calcDat(kr));int m = (l + r) >> 1;if (m > i) {r = m; k = kl;}else {l = m; k = kr;}}return Dat[k];}public long query(int l, int r) {if (l >= r) return E0;updown(l, r);long resL = E0, resR = E0;for (l += N, r += N; l < r; l >>= 1, r >>= 1) {if ((l & 1) != 0) resL = F.applyAsLong(resL, calcDat(l++));if ((r & 1) != 0) resR = F.applyAsLong(calcDat(--r), resR);}return F.applyAsLong(resL, resR);}private int updown(int l, int r) {if (l >= r) return 0;int i = 0;int kl = l + N, kr = r + N;for (int x = kl / (kl & -kl) >> 1, y = kr / (kr & -kr) >> 1; 0 < kl && kl < kr; kl >>= 1, kr >>= 1) {if (kl <= x) Stack[i++] = kl;if (kr <= y) Stack[i++] = kr;}for (; kl > 0; kl >>= 1) Stack[i++] = kl;int m = i;while (i > 0) calcDat(Stack[--i]);return m;}private long calcDat(int k) {long lz = Laz[k];if (lz != E1) {int w = N / Integer.highestOneBit(k);Dat[k] = G.applyAsLong(Dat[k], P.applyAsLong(lz, w));if (k < N) {int l = k << 1 | 0, r = k << 1 | 1;Laz[l] = H.applyAsLong(Laz[l], lz);Laz[r] = H.applyAsLong(Laz[r], lz);}Laz[k] = E1;}return Dat[k];}void debug(){for(int i = Dat.length - N ; i < Dat.length - 1; i ++ ){System.out.print(Dat[i]+" ");}System.out.println();}}final class WaveletMatrix {private final int[][] data;private final int n, bit;WaveletMatrix(int[] d, int bit) {n = d.length;this.bit = bit;int[] dat = d.clone();data = new int[bit][n];int[] que = new int[n];for (int k = bit - 1; k >= 0; k--) {int que1 = 0, que2 = n;for (int i = 0; i < n; i++) {if ((data[k][i] = (dat[i] >> k) & 1) == 1)que[--que2] = dat[i];elseque[que1++] = dat[i];}for (int i = 0; i < que1; i++)dat[i] = que[i];for (int i = n - 1, j = que1; i >= que1; i--, j++)dat[j] = que[i];for (int i = 1; i < n; i++)data[k][i] += data[k][i - 1];}}WaveletMatrix(int[] dat) {this(dat, 31);}private final int get(int bi, int id) {if (id == 0)return data[bi][0];return data[bi][id] - data[bi][id - 1];}final int access(int idx) {int ans = 0;for (int k = bit - 1; k >= 0; k--) {if (get(k, idx) == 1) {ans |= 1 << k;idx = zer(k, n) + one(k, idx);} elseidx -= data[k][idx];}return ans;}private final int one(int bi, int l) {if (l == 0)return 0;return data[bi][l - 1];}private final int zer(int bi, int l) {return l - one(bi, l);}private final int sum(int bi, int l, int r) {return one(bi, r) - one(bi, l);}public final int kth_smallest(int l, int r, int kth) {int ans = 0;for (int k = bit - 1; k >= 0; k--) {final int s = r - l - sum(k, l, r);if (kth < s) {l = zer(k, l);r = l + s;} else {kth -= s;ans |= 1 << k;final int ran = r - l - s;l = zer(k, n) + one(k, l);r = l + ran;}}return ans;}public final int kth_largest(int l, int r, int kth) {return kth_smallest(l, r, r - l - kth);}public final int count_lower(int l, int r, int lower) {int ans = 0;for (int k = bit - 1; k >= 0; k--) {final int s = r - l - sum(k, l, r);if (((lower >> k) & 1) == 1) {ans += s;final int ran = r - l - s;l = zer(k, n) + one(k, l);r = l + ran;} else {l = zer(k, l);r = l + s;}}return ans;}public final int count_upper(int l, int r, int upper) {return r - l - count_lower(l, r, upper + 1);}public final int count(int l, int r, int x) {return count_lower(l, r, x + 1) - count_lower(l, r, x);}public final int next_value(int l, int r, int upper) {final int cnt = count_lower(l, r, upper + 1);return kth_smallest(l, r, cnt);}public final int perv_value(int l, int r, int lower) {final int cnt = count_upper(l, r, lower - 1);return kth_largest(l, r, cnt);}}class UnionFind{private int [] rank , parents , size , data , edges;private int groups ;private BinaryOperator<Integer> op ;private static BinaryOperator<Integer> def_op = (a, b) -> a;UnionFind(int N) { this(N , def_op) ; }UnionFind(int N , BinaryOperator<Integer> op){this.rank = new int[N];this.parents = new int[N];this.size = new int[N];this.data = new int[N];this.edges = new int[N];this.groups = N ;for(int i = 0 ; i < N ; i ++ ){parents[i] = i ;rank[i] = 0 ;size[i] = 1 ;data[i] = i ;}this.op = op ;}int Group() { return this.groups ; }int Edge(int x) { return edges[root(x)] ; }int Op(int x) { return data[root(x)] ; }int Size(int x) { return size[root(x)] ; }int root(int x){if(x == parents[x]) return x ;else parents[x] = root(parents[x]);return parents[x];}boolean same(int x , int y) { return root(x) == root(y) ; }void unite(int l , int r){int left = root(l);int right = root(r);int parent = -1 , child = -1 ;if(left == right) { ++ edges[right]; return ; }parent = rank[left] > rank[right] ? left : right;child = rank[left] > rank[right] ? right : left ;--groups;parents[child] = parent ;rank[child] ++ ;size[parent] += size[child] ;edges[parent] += edges[child] + 1 ;data[parent] = op.apply(data[child] , data[parent]);}List<List<Integer>> Groups() {List<List<Integer>> Group = new ArrayList<>();Map<Integer,List<Integer>> mp = new HashMap<>();for(int i = 0 ; i < parents.length ; i ++ ){int par = root(i);if(!mp.containsKey(par)) mp.put(par , new ArrayList<>());mp.get(par).add(i);}for(List<Integer> lists : mp.values()) Group.add(new ArrayList<>(lists));return Group;}}class In{private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;}else{ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte()) return buffer[ptr++]; else return -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}private boolean hasNext() {while(hasNextByte() && !isPrintableChar(buffer[ptr])) {ptr++;}return hasNextByte();}public String next() {if (!hasNext()) throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while(isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext()) throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while(true){if ('0' <= b && b <= '9') {n *= 10;n += b - '0';}else if(b == -1 || !isPrintableChar(b)){return minus ? -n : n;}else{throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}public double nextDouble() {return Double.parseDouble(next());}public char nextChar() {return next().charAt(0);}public int [] IntArray(int n) {final int [] Array = new int [n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = nextInt();}return Array;}public int [][] IntArray(int n , int m) {final int [][] Array = new int [n][m];for(int i = 0 ; i < n ; i ++ ) {Array[i] = IntArray(m);}return Array;}public long [] LongArray(int n) {final long [] Array = new long [n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = nextLong();}return Array;}public long [][] LongArray(int n , int m) {final long [][] Array = new long [n][m];for(int i = 0 ; i < n ; i ++ ) {Array[i] = LongArray(m);}return Array;}public String [] StringArray(int n) {final String [] Array = new String [n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = next();}return Array;}public char [] CharArray(int n) {final char [] Array = new char[n];for(int i = 0 ; i < n ; i ++ ) {Array[i] = next().charAt(0);}return Array;}public char [][] CharArray(int n , int m) {final char [][] Array = new char [n][m];for(int i = 0 ; i < n ; i ++ ) {Array[i] = next().toCharArray();}return Array;}public char [][] CharArray2(int n , int m) {final char [][] Array = new char [n][m];for(int i = 0 ; i < n ; i ++ ) {for(int j = 0 ; j < m ; j ++ ) {Array[i][j] = next().charAt(0);}}return Array;}public List<Integer> [] Graph(int n) {@SuppressWarnings("unchecked")List<Integer> [] G = new ArrayList[n];for(int i = 0 ; i < n ; i ++ ) {G[i] = new ArrayList<>();}return G ;}}