結果
問題 |
No.444 旨味の相乗効果
|
ユーザー |
![]() |
提出日時 | 2024-12-22 15:33:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 2,500 ms |
コード長 | 1,693 bytes |
コンパイル時間 | 1,633 ms |
コンパイル使用メモリ | 168,328 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-22 15:33:04 |
合計ジャッジ時間 | 3,099 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #define int long long using namespace std; void file_IO(){ freopen("spice.in", "r", stdin); freopen("spice.out", "w", stdout); } const int N = 85; const int MOD = 1e9 + 7; int n, c, ans = 0, v[N]; int fp(int x, int y){ int res = 1; while (y){ if (y & 1) res = res * x % MOD; x = x * x % MOD, y >>= 1; } return res; } void add(int &x, int y){ x = (x + y >= MOD ? x + y - MOD : x + y); } void sub(int &x, int y){ x = (x >= y ? x - y : x + MOD - y); } struct matrix{ int a[N][N]; matrix(){ memset(a, 0, sizeof(a)); } matrix operator * (const matrix& b) const{ matrix c; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) add(c.a[i][j], a[i][k] * b.a[k][j] % MOD); return c; } void print(){ cout << "Size: " << n << " * " << n << endl; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++) cout << a[i][j] << " " ; cout << endl; } } }res, base; void calc(int x){ while (x){ if (x & 1) res = res * base; base = base * base, x >>= 1; } } signed main(){ //file_IO(); cin >> n >> c; for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1; i <= n; i++) res.a[1][i] = v[i]; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) base.a[i][j] = (i <= j ? v[j] : 0); calc(c - 1); for (int i = 1; i <= n; i++) add(ans, res.a[1][i]); for (int i = 1; i <= n; i++) sub(ans, fp(v[i], c)); cout << ans << endl; return 0; }