結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
![]() |
提出日時 | 2021-11-19 22:32:44 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,637 ms / 2,000 ms |
コード長 | 1,525 bytes |
コンパイル時間 | 2,310 ms |
コンパイル使用メモリ | 79,712 KB |
実行使用メモリ | 54,472 KB |
最終ジャッジ日時 | 2025-01-01 19:28:13 |
合計ジャッジ時間 | 22,535 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
import java.io.*;import java.util.*;class Main{public static void main(String args[])throws Exception{BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));StringBuilder sb=new StringBuilder();String s[]=bu.readLine().split(" ");int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]); long t=Long.parseLong(s[2]);int i; long a[][]=new long[n][n];for(i=0;i<m;i++){s=bu.readLine().split(" ");int u=Integer.parseInt(s[0]),v=Integer.parseInt(s[1]);a[u][v]=a[v][u]=1;}long ans[][]=power(a,t),dp[][]=new long[1][n];dp[0][0]=1;multiply(dp,ans);System.out.println(dp[0][0]);}static long temp[][]=new long[100][100],M=998244353;static void multiply(long a[][],long b[][]){int i,j,k,n=a.length,m=a[0].length,l=b[0].length;for(i=0;i<n;i++)for(j=0;j<l;j++){temp[i][j]=0;for(k=0;k<m;k++)temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%M;}//in out problem n==m==kfor(i=0;i<n;i++)for(j=0;j<l;j++)a[i][j]=temp[i][j];}static long[][] power(long a[][],long b){int i,n=a.length;long res[][]=new long[n][n];for(i=0;i<n;i++) res[i][i]=1;while(b!=0){if(b%2==1) multiply(res,a);b>>=1;multiply(a,a);}return res;}}