結果
問題 |
No.444 旨味の相乗効果
|
ユーザー |
|
提出日時 | 2025-03-30 14:34:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 2,500 ms |
コード長 | 1,261 bytes |
コンパイル時間 | 2,165 ms |
コンパイル使用メモリ | 195,020 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-30 14:34:16 |
合計ジャッジ時間 | 6,164 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 23 |
ソースコード
#include<bits/stdc++.h> #define ll long long using namespace std; inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch&15); ch=getchar(); } return x*f; } inline void write(ll x) { if(x<0) { putchar('-'); x=-x; } if(x>9)write(x/10); putchar(x%10+'0'); return; } const ll mod=1000000007; ll n,c,a[82]; struct Matrix { ll a[82][82]; Matrix(){memset(a,0,sizeof a);} inline Matrix operator*(Matrix b) { Matrix res; for(int i=1;i<=81;++i) for(int j=1;j<=81;++j) for(int k=1;k<=81;++k) res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod; return res; } }ans,base; inline void qpow(ll y) { while(y) { if(y&1)ans=base*ans; base=base*base; y>>=1; } } inline ll qpow(ll x,ll y) { ll res=1; while(y) { if(y&1)res=(res*x)%mod; x=(x*x)%mod; y>>=1; } return res; } int main() { n=read(),c=read(); for(int i=1;i<=n;++i)a[i]=read(),ans.a[i][1]=1; for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) base.a[j][i]=a[i]; qpow(c); ll res=ans.a[n][1]; for(int i=1;i<=n;++i)res=(res-qpow(a[i],c)+mod)%mod; write(res); return 0; }