結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
![]() |
提出日時 | 2021-11-19 21:47:44 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,746 ms / 2,000 ms |
コード長 | 1,385 bytes |
コンパイル時間 | 2,415 ms |
コンパイル使用メモリ | 77,832 KB |
実行使用メモリ | 58,864 KB |
最終ジャッジ日時 | 2024-12-31 22:48:21 |
合計ジャッジ時間 | 26,176 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
import java.util.Scanner;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();long t = sc.nextLong();long[][] a = new long[n][n];for (int i = 0; i < m; i++) {int u = sc.nextInt();int v = sc.nextInt();a[u][v] = 1;a[v][u] = 1;}sc.close();int mod = 998244353;long[][] b = matrixPow(a, t, mod);long[] c = new long[n];c[0] = 1;long[] d = matrixMul1(c, b, mod);System.out.println(d[0]);}static long[][] matrixPow(long[][] a, long k, int m) {if (k == 1) {return a;}long[][] ret = matrixPow(a, k / 2, m);ret = matrixMul(ret, ret, m);if (k % 2 == 1) {ret = matrixMul(ret, a, m);}return ret;}static long[][] matrixMul(long[][] a, long[][] b, int m) {int h = a.length;int w = b[0].length;int n = a[0].length;long[][] c = new long[h][w];for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {for (int x = 0; x < n; x++) {c[i][j] += a[i][x] * b[x][j];c[i][j] %= m;}}}return c;}static long[] matrixMul1(long[] a, long[][] b, int m) {int w = b[0].length;int n = a.length;long[] c = new long[w];for (int j = 0; j < w; j++) {for (int x = 0; x < n; x++) {c[j] += a[x] * b[x][j];c[j] %= m;}}return c;}}