結果
問題 |
No.1105 Many Triplets
|
ユーザー |
|
提出日時 | 2025-03-26 18:50:54 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 2,803 bytes |
コンパイル時間 | 4,178 ms |
コンパイル使用メモリ | 81,880 KB |
実行使用メモリ | 39,268 KB |
最終ジャッジ日時 | 2025-03-26 18:51:02 |
合計ジャッジ時間 | 7,065 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
import java.io.*; import java.util.StringTokenizer; /** * Date: 2025/3/26 17:47 */ public class Main { static int n;//矩阵的长度和宽度 n * n 的矩阵 static int mod = (int) (1e9 + 7); static long[][] A; static long[][] res; //两矩阵相乘 static long[][] multi(long[][] a, long[][] b) { long[][] t = new long[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { t[i][j] += a[i][k] * b[k][j]; t[i][j] %= mod; } } } return t; } //k 个矩阵相乘 static void quickPow(long k) { for (int i = 0; i < n; i++) res[i][i] = 1;//构造单位矩阵 while (k > 0) { if ((k & 1) == 1) res = multi(res, A); A = multi(A, A); k >>= 1; } } //入口,传入一个矩阵和一个整数 k ,返回该矩阵的 k 次幂 static long[][] getRes(int[][] a, long k) { n = a.length; A = new long[n][n]; res = new long[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { A[i][j] = a[i][j]; } } quickPow(k); return res; } public static void main(String[] args) { long n = sc.nextLong(); int[] a = new int[3]; for (int i = 0; i < 3; i++) { a[i] = sc.nextInt(); } int[][] mat = {{1, -1, 0}, {0, 1, -1}, {-1, 0, 1}}; long[][] z = getRes(mat, n - 1); for (int i = 0; i < 3; i++) { long v = 0; for (int j = 0; j < 3; j++) { v += z[i][j] * a[j]; } v = (v % mod + mod) % mod; out.print(v+" "); } out.close(); } static Kattio sc = new Kattio(); static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); static class Kattio { static BufferedReader r; static StringTokenizer st; public Kattio() { r = new BufferedReader(new InputStreamReader(System.in)); } public String next() { try { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(r.readLine()); } return st.nextToken(); } catch (Exception e) { return null; } } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } } }