結果
問題 | No.444 旨味の相乗効果 |
ユーザー | hermione17 |
提出日時 | 2016-11-11 23:53:44 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 951 ms / 2,500 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 4,543 ms |
コンパイル使用メモリ | 74,668 KB |
実行使用メモリ | 45,152 KB |
最終ジャッジ日時 | 2023-08-16 20:10:12 |
合計ジャッジ時間 | 19,382 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 169 ms
40,380 KB |
testcase_01 | AC | 173 ms
40,560 KB |
testcase_02 | AC | 168 ms
40,380 KB |
testcase_03 | AC | 197 ms
41,460 KB |
testcase_04 | AC | 951 ms
44,524 KB |
testcase_05 | AC | 224 ms
42,112 KB |
testcase_06 | AC | 173 ms
40,836 KB |
testcase_07 | AC | 254 ms
44,108 KB |
testcase_08 | AC | 260 ms
43,780 KB |
testcase_09 | AC | 367 ms
44,120 KB |
testcase_10 | AC | 362 ms
44,000 KB |
testcase_11 | AC | 325 ms
43,504 KB |
testcase_12 | AC | 540 ms
44,608 KB |
testcase_13 | AC | 525 ms
44,864 KB |
testcase_14 | AC | 551 ms
44,468 KB |
testcase_15 | AC | 560 ms
44,580 KB |
testcase_16 | AC | 905 ms
44,680 KB |
testcase_17 | AC | 792 ms
44,276 KB |
testcase_18 | AC | 841 ms
45,148 KB |
testcase_19 | AC | 762 ms
44,612 KB |
testcase_20 | AC | 752 ms
44,508 KB |
testcase_21 | AC | 127 ms
39,900 KB |
testcase_22 | AC | 128 ms
39,972 KB |
testcase_23 | AC | 906 ms
45,152 KB |
testcase_24 | AC | 134 ms
40,064 KB |
testcase_25 | AC | 752 ms
44,568 KB |
testcase_26 | AC | 494 ms
44,304 KB |
testcase_27 | AC | 888 ms
44,688 KB |
ソースコード
import java.io.PrintStream; import java.util.Scanner; public class Y444 { Scanner in = new Scanner(System.in); PrintStream out = new PrintStream(System.out); long MOD = 1000000007; Y444() throws Exception { int n = in.nextInt(); long c = in.nextLong(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); } Matrix m = new Matrix(); for (int i = 0; i < n; i++) { m.a[i][i] = a[i]; m.a[i+n][i+n] = a[i]; for (int j = 0; j < i; j++) { m.a[i+n][j] = a[i]; m.a[i+n][j+n] = a[i]; } } Matrix power = m.pow(c - 1); long ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans = (ans + a[j] * power.a[i+n][j]) % MOD; } } power=m.mul(m); out.println(ans); } public static void main(String argv[]) throws Exception { new Y444(); } class Matrix { long[][] a = new long[160][160]; Matrix mul(Matrix that) { Matrix ret = new Matrix(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length; j++) { for (int k = 0; k < a.length; k++) { ret.a[i][k] = (ret.a[i][k] + a[i][j] * that.a[j][k]); } if ((j & 7) == 7) { for (int k = 0; k < a.length; k++) { ret.a[i][k] %= MOD; } } } } return ret; } Matrix pow(long p) { Matrix ret = new Matrix(); Matrix x = this; for (int i = 0; i < a.length; i++) { ret.a[i][i] = 1; } while (p > 0) { if ((p & 1) == 1) { ret = x.mul(ret); } x = x.mul(x); p >>= 1; } return ret; } } }