結果
問題 | No.856 増える演算 |
ユーザー | tempura_pp |
提出日時 | 2019-07-26 22:00:33 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 201 ms / 3,153 ms |
コード長 | 2,435 bytes |
コンパイル時間 | 1,650 ms |
コンパイル使用メモリ | 112,092 KB |
実行使用メモリ | 22,264 KB |
最終ジャッジ日時 | 2024-04-18 00:34:01 |
合計ジャッジ時間 | 11,188 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
21,488 KB |
testcase_01 | AC | 58 ms
21,440 KB |
testcase_02 | AC | 57 ms
21,488 KB |
testcase_03 | AC | 56 ms
21,428 KB |
testcase_04 | AC | 54 ms
21,444 KB |
testcase_05 | AC | 57 ms
21,460 KB |
testcase_06 | AC | 57 ms
21,364 KB |
testcase_07 | AC | 55 ms
21,384 KB |
testcase_08 | AC | 58 ms
21,456 KB |
testcase_09 | AC | 57 ms
21,392 KB |
testcase_10 | AC | 57 ms
21,360 KB |
testcase_11 | AC | 56 ms
21,300 KB |
testcase_12 | AC | 57 ms
21,296 KB |
testcase_13 | AC | 56 ms
21,456 KB |
testcase_14 | AC | 57 ms
21,360 KB |
testcase_15 | AC | 56 ms
21,360 KB |
testcase_16 | AC | 56 ms
21,468 KB |
testcase_17 | AC | 57 ms
21,368 KB |
testcase_18 | AC | 55 ms
21,360 KB |
testcase_19 | AC | 57 ms
21,364 KB |
testcase_20 | AC | 57 ms
21,360 KB |
testcase_21 | AC | 57 ms
21,480 KB |
testcase_22 | AC | 58 ms
21,360 KB |
testcase_23 | AC | 62 ms
21,412 KB |
testcase_24 | AC | 65 ms
21,428 KB |
testcase_25 | AC | 58 ms
21,500 KB |
testcase_26 | AC | 57 ms
21,476 KB |
testcase_27 | AC | 57 ms
21,492 KB |
testcase_28 | AC | 61 ms
21,408 KB |
testcase_29 | AC | 61 ms
21,396 KB |
testcase_30 | AC | 60 ms
21,456 KB |
testcase_31 | AC | 56 ms
21,336 KB |
testcase_32 | AC | 61 ms
21,416 KB |
testcase_33 | AC | 69 ms
21,424 KB |
testcase_34 | AC | 82 ms
21,548 KB |
testcase_35 | AC | 73 ms
21,436 KB |
testcase_36 | AC | 81 ms
21,560 KB |
testcase_37 | AC | 78 ms
21,524 KB |
testcase_38 | AC | 58 ms
21,372 KB |
testcase_39 | AC | 60 ms
21,496 KB |
testcase_40 | AC | 65 ms
21,392 KB |
testcase_41 | AC | 66 ms
21,556 KB |
testcase_42 | AC | 87 ms
21,696 KB |
testcase_43 | AC | 66 ms
21,440 KB |
testcase_44 | AC | 56 ms
21,436 KB |
testcase_45 | AC | 59 ms
21,392 KB |
testcase_46 | AC | 67 ms
21,568 KB |
testcase_47 | AC | 66 ms
21,556 KB |
testcase_48 | AC | 74 ms
21,444 KB |
testcase_49 | AC | 68 ms
21,580 KB |
testcase_50 | AC | 75 ms
21,516 KB |
testcase_51 | AC | 83 ms
21,488 KB |
testcase_52 | AC | 85 ms
21,592 KB |
testcase_53 | AC | 131 ms
21,760 KB |
testcase_54 | AC | 94 ms
21,616 KB |
testcase_55 | AC | 130 ms
21,804 KB |
testcase_56 | AC | 86 ms
21,500 KB |
testcase_57 | AC | 138 ms
21,792 KB |
testcase_58 | AC | 119 ms
21,664 KB |
testcase_59 | AC | 183 ms
21,972 KB |
testcase_60 | AC | 101 ms
21,584 KB |
testcase_61 | AC | 172 ms
21,992 KB |
testcase_62 | AC | 161 ms
22,036 KB |
testcase_63 | AC | 61 ms
21,384 KB |
testcase_64 | AC | 150 ms
21,972 KB |
testcase_65 | AC | 82 ms
21,400 KB |
testcase_66 | AC | 100 ms
21,664 KB |
testcase_67 | AC | 119 ms
21,656 KB |
testcase_68 | AC | 155 ms
21,840 KB |
testcase_69 | AC | 156 ms
21,876 KB |
testcase_70 | AC | 179 ms
22,060 KB |
testcase_71 | AC | 156 ms
22,000 KB |
testcase_72 | AC | 138 ms
21,808 KB |
testcase_73 | AC | 199 ms
22,096 KB |
testcase_74 | AC | 198 ms
22,264 KB |
testcase_75 | AC | 197 ms
22,136 KB |
testcase_76 | AC | 199 ms
22,196 KB |
testcase_77 | AC | 200 ms
22,096 KB |
testcase_78 | AC | 201 ms
22,140 KB |
testcase_79 | AC | 201 ms
22,232 KB |
testcase_80 | AC | 199 ms
22,076 KB |
testcase_81 | AC | 198 ms
22,200 KB |
testcase_82 | AC | 152 ms
22,192 KB |
ソースコード
#include<iostream> #include<string> #include<algorithm> #include<vector> #include<iomanip> #include<math.h> #include<complex> #include<queue> #include<deque> #include<stack> #include<map> #include<set> #include<bitset> #include<functional> #include<assert.h> #include<numeric> using namespace std; #define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i ) #define rep(i,n) REP(i,0,n) using ll = long long; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; typedef vector<complex<double>> poly; const double pi=acos(-1); poly dft(poly f,int rev){ int n=f.size(); int j=0; REP(i,1,n-1){ for(int k=n/2;k>(j^=k);k>>=1); if(i<j)swap(f[i],f[j]); } complex<double> zeta,ret,t,s; for(int i=1;i<n;i<<=1){ zeta=polar(1.0,pi/i*rev); for(int j=0;j<n;j+=2*i){ ret=1.0; rep(k,i){ s=f[j+k]; t=f[j+k+i]; t=complex<double>(t.real()*ret.real()-t.imag()*ret.imag(),t.imag()*ret.real()+t.real()*ret.imag()); f[j+k]=s+t; f[j+k+i]=s-t; ret*=zeta; } } } if(rev==-1)rep(i,n)f[i]/=n; return f; } poly fft(poly g,poly h){ poly f; int m=(int)g.size()+h.size()+1; int sz=1; while(sz<m)sz*=2; f.resize(sz,0); g.resize(sz,0); h.resize(sz,0); g=dft(g,1); h=dft(h,1); rep(i,sz)f[i]=g[i]*h[i]; f=dft(f,-1); return f; } ll powmod(ll n,ll k){ k%=mod-1; if(k<0)k+=mod-1; ll ret=1; while(k){ if(k&1)ret=ret*n%mod; n=n*n%mod; k>>=1; } return ret; } int main(){ int n; cin>>n; ll a[n]; rep(i,n)cin>>a[i]; poly f(100001); rep(i,n)f[a[i]]+=1; poly res = fft(f,f); rep(i,n){ res[2*a[i]]-=1.0; } ll ans = 1; rep(i,200001){ ans*=powmod(i,(ll)(res[i].real()+.5)/2); ans%=mod; } ll sum = 0; ll mi = inf; vector<pair<double,double>> v; for(int i=n-1;i>=0;i--){ ans*=powmod(a[i],sum); ans%=mod; sum+=a[i]; v.emplace_back(a[i],mi); mi=min(a[i],mi); } sort(v.begin(),v.end(),[](auto x,auto y){ return log(x.first)*x.second+log(x.first+x.second)<log(y.first)*y.second+log(y.first+y.second); }); ans*=powmod(v[0].first+v[0].second,mod-2); ans%=mod; ans*=powmod(v[0].first,mod-1-v[0].second); ans%=mod; cout<<ans<<endl; return 0; }