結果
問題 | No.856 増える演算 |
ユーザー | tempura_pp |
提出日時 | 2019-07-26 21:46:41 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,316 bytes |
コンパイル時間 | 1,196 ms |
コンパイル使用メモリ | 106,896 KB |
実行使用メモリ | 22,316 KB |
最終ジャッジ日時 | 2023-09-15 01:03:32 |
合計ジャッジ時間 | 11,271 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
21,276 KB |
testcase_01 | AC | 56 ms
21,312 KB |
testcase_02 | AC | 56 ms
21,100 KB |
testcase_03 | WA | - |
testcase_04 | AC | 57 ms
21,268 KB |
testcase_05 | AC | 55 ms
21,204 KB |
testcase_06 | WA | - |
testcase_07 | AC | 57 ms
21,084 KB |
testcase_08 | AC | 56 ms
21,436 KB |
testcase_09 | AC | 57 ms
21,092 KB |
testcase_10 | AC | 56 ms
21,268 KB |
testcase_11 | AC | 57 ms
21,108 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 57 ms
21,148 KB |
testcase_20 | AC | 57 ms
21,240 KB |
testcase_21 | AC | 56 ms
21,024 KB |
testcase_22 | AC | 57 ms
21,108 KB |
testcase_23 | AC | 58 ms
21,136 KB |
testcase_24 | AC | 59 ms
21,216 KB |
testcase_25 | AC | 57 ms
21,180 KB |
testcase_26 | AC | 57 ms
21,100 KB |
testcase_27 | AC | 56 ms
21,168 KB |
testcase_28 | AC | 58 ms
21,316 KB |
testcase_29 | AC | 58 ms
21,068 KB |
testcase_30 | AC | 59 ms
21,304 KB |
testcase_31 | AC | 57 ms
21,420 KB |
testcase_32 | AC | 58 ms
21,160 KB |
testcase_33 | AC | 61 ms
21,340 KB |
testcase_34 | AC | 68 ms
21,396 KB |
testcase_35 | AC | 64 ms
21,256 KB |
testcase_36 | AC | 68 ms
21,672 KB |
testcase_37 | AC | 66 ms
21,324 KB |
testcase_38 | AC | 57 ms
21,444 KB |
testcase_39 | AC | 58 ms
21,560 KB |
testcase_40 | AC | 61 ms
21,176 KB |
testcase_41 | AC | 61 ms
21,108 KB |
testcase_42 | AC | 69 ms
21,328 KB |
testcase_43 | AC | 61 ms
21,176 KB |
testcase_44 | AC | 57 ms
21,124 KB |
testcase_45 | AC | 58 ms
21,056 KB |
testcase_46 | AC | 61 ms
21,388 KB |
testcase_47 | AC | 60 ms
21,504 KB |
testcase_48 | AC | 63 ms
21,232 KB |
testcase_49 | AC | 61 ms
21,404 KB |
testcase_50 | AC | 64 ms
21,560 KB |
testcase_51 | AC | 67 ms
21,708 KB |
testcase_52 | AC | 67 ms
21,396 KB |
testcase_53 | WA | - |
testcase_54 | AC | 79 ms
21,440 KB |
testcase_55 | WA | - |
testcase_56 | AC | 77 ms
21,244 KB |
testcase_57 | AC | 98 ms
21,736 KB |
testcase_58 | AC | 88 ms
21,596 KB |
testcase_59 | AC | 111 ms
21,988 KB |
testcase_60 | WA | - |
testcase_61 | AC | 112 ms
21,944 KB |
testcase_62 | AC | 106 ms
21,640 KB |
testcase_63 | AC | 63 ms
21,112 KB |
testcase_64 | AC | 102 ms
21,644 KB |
testcase_65 | WA | - |
testcase_66 | AC | 82 ms
21,308 KB |
testcase_67 | WA | - |
testcase_68 | AC | 105 ms
21,572 KB |
testcase_69 | AC | 103 ms
21,608 KB |
testcase_70 | AC | 117 ms
21,824 KB |
testcase_71 | AC | 107 ms
21,660 KB |
testcase_72 | WA | - |
testcase_73 | AC | 122 ms
21,904 KB |
testcase_74 | AC | 122 ms
22,140 KB |
testcase_75 | AC | 123 ms
21,900 KB |
testcase_76 | AC | 122 ms
22,144 KB |
testcase_77 | AC | 122 ms
22,044 KB |
testcase_78 | WA | - |
testcase_79 | AC | 121 ms
22,072 KB |
testcase_80 | AC | 121 ms
21,980 KB |
testcase_81 | AC | 121 ms
21,948 KB |
testcase_82 | AC | 101 ms
21,924 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; for(int i=n-1;i>=0;i--){ ans*=powmod(a[i],sum); ans%=mod; sum+=a[i]; } sort(a,a+n); ans*=powmod(a[0]+a[1],mod-2); ans%=mod; if(a[0]==2){ if(a[1]==3)ans*=powmod(8,mod-2); else ans*=powmod(a[1],mod-3); ans%=mod; } else if(a[0]>=3){ ans*=powmod(a[1],mod-a[0]-1); ans%=mod; } cout<<ans<<endl; return 0; }