結果
問題 |
No.444 旨味の相乗効果
|
ユーザー |
![]() |
提出日時 | 2021-03-29 18:06:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,678 bytes |
コンパイル時間 | 6,654 ms |
コンパイル使用メモリ | 392,200 KB |
実行使用メモリ | 41,508 KB |
最終ジャッジ日時 | 2024-11-29 10:17:37 |
合計ジャッジ時間 | 16,462 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 RE * 2 |
other | AC * 2 WA * 5 RE * 15 TLE * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; template<typename type> class Matrix{ public: vector<vector<type>> value; Matrix(vector<vector<type>> e){ value=e; } Matrix<type> operator * (Matrix a){ vector<vector<type>> ret(value.size(),vector<type>(a.value[0].size())); type temp; for(int i=value.size()-1;i>=0;i--){ for(int j=a.value[0].size()-1;j>=0;j--){ temp=0; for(int k=a.value.size()-1;k>=0;k--){ temp+=value[i][k]*a.value[k][j]; } ret[i][j]=temp; } } return Matrix(ret); } Matrix<type> pow(int p){ Matrix temp=value; Matrix ans=temp; bool flg=false; while(p>0){ if(p%2){ if(flg){ ans=ans*temp; }else{ flg=true; ans=temp; } } p=p/2; temp=temp*temp; } return ans; } }; int main(){ int n,c; cin>>n>>c; Matrix<mp::cpp_int> b(vector<vector<mp::cpp_int>>(n,vector<mp::cpp_int>(1,1))); vector<vector<mp::cpp_int>> Av(n,vector<mp::cpp_int>(n,0)); vector<mp::cpp_int> a(c); for(int i=0;i<c;i++){ cin>>a[i]; } for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ Av[i][j]=a[j]; } } Matrix<mp::cpp_int> A(Av); mp::cpp_int ans=(A.pow(c)*b).value[n-1][0]; for(int i=0;i<n;i++){ ans-=pow(a[i],n); } cout<<ans<<endl; }