結果
問題 |
No.444 旨味の相乗効果
|
ユーザー |
|
提出日時 | 2016-11-12 02:23:24 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 348 ms / 2,500 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 3,851 ms |
コンパイル使用メモリ | 77,968 KB |
実行使用メモリ | 45,532 KB |
最終ジャッジ日時 | 2024-06-24 20:54:36 |
合計ジャッジ時間 | 9,116 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
package yukicoder; import java.util.*; public class Q444 { static final long MODULO = 1_000_000_000 + 7; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long c = sc.nextLong(); long[] a = new long[n]; for (int i = 0; i < n; ++i) { a[i] = sc.nextLong() % MODULO; } long[][] vec = new long[n][1]; for (int i = 0; i < n; ++i) { vec[i][0] = 1; } long[][] mx = new long[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { mx[i][j] = a[j]; } } vec = pow(mx, vec, c); long ans = vec[n - 1][0]; for (int i = 0; i < n; ++i) { ans = (ans - pow(a[i], c) + MODULO) % MODULO; } System.out.println(ans); } static long[][] pow(long[][] mx, long[][] vec, long n) { for (; n > 0; n >>= 1, mx = mul(mx, mx)) { if (n % 2 == 1) { vec = mul(mx, vec); } } return vec; } static long pow(long a, long n) { long ret = 1; for (; n > 0; n >>= 1, a = (a * a) % MODULO) { if (n % 2 == 1) { ret = (ret * a) % MODULO; } } return ret; } static long[][] mul(long[][] A, long[][] B) { if (A[0].length != B.length) throw new AssertionError(); int mid = A[0].length; long[][] ret = new long[A.length][B[0].length]; for (int i = 0; i < A.length; ++i) { for (int j = 0; j < B[0].length; ++j) { for (int k = 0; k < mid; ++k) { ret[i][j] += A[i][k] * B[k][j] % MODULO; ret[i][j] %= MODULO; } } } return ret; } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }