結果
問題 | No.444 旨味の相乗効果 |
ユーザー |
![]() |
提出日時 | 2016-11-12 01:26:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,500 ms |
コード長 | 1,842 bytes |
コンパイル時間 | 995 ms |
コンパイル使用メモリ | 93,668 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-24 20:53:38 |
合計ジャッジ時間 | 2,165 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <iostream> #include <algorithm> #include <stack> #include <queue> #include <vector> #include <set> #include <map> #include <bitset> #include <functional> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back(a) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<(x)<<endl #define fi first #define se second #define INF 2147483600 #define MOD 1000000007 #define MAT_N 80 long mat[MAT_N][MAT_N]; // a * b = dst O(N^3) aのほうが疎な行列だとbetter long tmp[MAT_N][MAT_N]; void mat_mul(long a[][MAT_N], long b[][MAT_N], long dst[][MAT_N]){ fill(tmp[0], tmp[MAT_N], 0); rep(i,MAT_N) rep(k,MAT_N) if(a[i][k]!=0) rep(j,MAT_N){ tmp[i][j] += a[i][k] * b[k][j] % MOD; } rep(i,MAT_N) rep(j,MAT_N) dst[i][j] = tmp[i][j] % MOD; } // a^n = dst O(M^3 log N) long tmp_pow[MAT_N][MAT_N]; void mat_pow(long a[][MAT_N], long n, long dst[][MAT_N]){ rep(i,MAT_N) rep(j,MAT_N) tmp_pow[i][j] = a[i][j]; fill(dst[0], dst[MAT_N], 0); rep(i,MAT_N) dst[i][i]=1; while(n>0){ if(n&1) mat_mul(tmp_pow, dst, dst); mat_mul(tmp_pow, tmp_pow, tmp_pow); n /= 2; } } // x^n mod long mod_pow(long x, long n, long mod){ long res=1; x %= mod; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } int main(){ int n; long c; cin>>n>>c; vector<long> vec(n); rep(i,n) scanf("%ld", &vec[i]); fill(mat[0], mat[n], 0); rep(i,n) rep(j,i+1) mat[i][j]=vec[i]; mat_pow(mat, c-1, mat); long res=0; rep(i,n){ rep(j,n) res += mat[i][j]*vec[j] % MOD; res -= mod_pow(vec[i], c, MOD); } while(res<0) res+=MOD; cout << res%MOD <<endl; return 0; }