結果
問題 | No.444 旨味の相乗効果 |
ユーザー |
![]() |
提出日時 | 2021-03-30 10:41:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,901 bytes |
コンパイル時間 | 7,995 ms |
コンパイル使用メモリ | 393,500 KB |
実行使用メモリ | 38,436 KB |
最終ジャッジ日時 | 2024-11-30 07:58:41 |
合計ジャッジ時間 | 22,838 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 WA * 1 |
other | AC * 5 WA * 15 TLE * 3 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; template<typename type=int> 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; } }; mp::cpp_int p(mp::cpp_int a,mp::cpp_int n){ mp::cpp_int ans=1; mp::cpp_int temp=a; while(n>0){ if(n%2){ ans*=temp; } temp=temp*temp; n=n/2; } 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(n); for(int i=0;i<n;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-=p(a[i],c); } cout<<ans<<endl; }