結果
問題 | No.1102 Remnants |
ユーザー |
![]() |
提出日時 | 2020-07-03 21:44:01 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 3,130 bytes |
コンパイル時間 | 2,227 ms |
コンパイル使用メモリ | 164,192 KB |
実行使用メモリ | 37,740 KB |
最終ジャッジ日時 | 2024-11-30 18:57:12 |
合計ジャッジ時間 | 5,107 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
//#include <bits/stdc++.h> #include "bits/stdc++.h" using namespace std; typedef long long ll; /* #include "boost/multiprecision/cpp_int.hpp" #include "boost/multiprecision/cpp_dec_float.hpp" namespace mp = boost::multiprecision; typedef mp::cpp_int LL; typedef mp::number<mp::cpp_dec_float<1024>> DD;// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする) */ typedef long double dd; #define i_7 (ll)(1E9+7) //#define i_7 998244353 #define i_5 i_7-2 ll mod(ll a){ ll c=a%i_7; if(c>=0)return c; return c+i_7; } typedef pair<ll,ll> l_l; typedef pair<dd,dd> d_d; ll inf=(ll)1E16; #define rep(i,l,r) for(ll i=l;i<=r;i++) #define rrep(i,r,l) for(ll i=r;i>=l;i--) #define pb push_back ll max(ll a,ll b){if(a<b)return b;else return a;} ll min(ll a,ll b){if(a>b)return b;else return a;} void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]); void Min(ll &pos,ll val){pos=min(pos,val);} void Add(ll &pos,ll val){pos=mod(pos+val);} dd EPS=1E-9; #define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define fi first #define se second #define endl "\n" //インタラクティブで消す!!!!!!!!!!!!!!!!!!!!! #define SORT(v) sort(v.begin(),v.end()) #define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end()) #define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin()) #define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin()) template<class T,class S> inline bool chmax(T &a, S b) { if(a < b) { a = b; return true; } return false; } template<class T,class S> inline bool chmin(T &a, S b) { if(a > b) { a = b; return true; } return false; } void mod_print(ll k){ ll P=1000; rep(y,1,P){ ll x=mod(y*k); if(x+P>=i_7){ x-=i_7; } if(abs(x)<=P){ //cout<<x<<"/"<<y; cout<<setprecision(5)<<(dd)x/(dd)y; return; } } cout<<"nun"<<endl; } #define all(c) c.begin(),c.end() ////////////////////////// ll po(ll i,ll p){ if(p==0)return 1; else{ i=mod(i); if(p==1)return i; if(p%2==0)return po(mod(i*i),p/2); return mod(i*po(i,p-1)); } } ll bunbo(ll n){ return po(n,i_5); } #define N 2000004 ll kai[N]; ll kai2[N]; void calc(){ kai[0]=1; kai2[0]=1; rep(i,1,N-1){ kai[i]=mod(kai[i-1]*i); } kai2[N-1]=po(kai[N-1],i_5); for(ll i=N-2;i>=0;i--){ kai2[i]=mod(kai2[i+1]*(i+1)); } } ll comb(ll n,ll k){ if(n<k)return 0; if(n==0)return 1; return mod(mod(kai[n]*kai2[n-k])*kai2[k]); } int main(){fastio calc(); ll n,k;cin>>n>>k; ll a[n];rep(i,0,n-1)cin>>a[i]; ll dp[n]; memset(dp,0,sizeof(dp)); ll res=1; rep(i,0,n-1){ if(i>=1){ res=mod(mod(res*(k-1+i))*bunbo(i)); } dp[i]=res; } rep(i,1,n-1)Add(dp[i],dp[i-1]); //rep(i,0,n-1)cout<<dp[i]<<" ";cout<<endl; ll ans=0; rep(i,0,n-1){ Add(ans,mod(mod(a[i]*dp[i])*dp[n-1-i])); } cout<<mod(ans)<<endl; return 0; }