#362748 (C++11) No.856 増える演算

提出ソース

結果

問題	No.856 増える演算
ユーザー	chocorusk
提出日時	2019-07-26 22:38:38
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	156 ms / 3,153 ms
コード長	2,734 bytes
コンパイル時間	1,121 ms
コンパイル使用メモリ	109,248 KB
実行使用メモリ	21,508 KB
最終ジャッジ日時	2023-09-15 02:34:50
合計ジャッジ時間	12,845 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	88 ms 20,768 KB
testcase_01	AC	89 ms 20,708 KB
testcase_02	AC	88 ms 21,132 KB
testcase_03	AC	88 ms 21,076 KB
testcase_04	AC	89 ms 20,720 KB
testcase_05	AC	89 ms 20,828 KB
testcase_06	AC	90 ms 20,924 KB
testcase_07	AC	90 ms 20,716 KB
testcase_08	AC	89 ms 20,768 KB
testcase_09	AC	89 ms 20,720 KB
testcase_10	AC	89 ms 20,764 KB
testcase_11	AC	89 ms 20,772 KB
testcase_12	AC	89 ms 20,928 KB
testcase_13	AC	88 ms 20,772 KB
testcase_14	AC	88 ms 20,884 KB
testcase_15	AC	89 ms 20,924 KB
testcase_16	AC	88 ms 20,884 KB
testcase_17	AC	89 ms 20,764 KB
testcase_18	AC	88 ms 20,884 KB
testcase_19	AC	88 ms 21,080 KB
testcase_20	AC	88 ms 20,720 KB
testcase_21	AC	88 ms 20,724 KB
testcase_22	AC	88 ms 20,928 KB
testcase_23	AC	90 ms 20,744 KB
testcase_24	AC	91 ms 20,800 KB
testcase_25	AC	89 ms 20,852 KB
testcase_26	AC	90 ms 20,812 KB
testcase_27	AC	91 ms 20,924 KB
testcase_28	AC	90 ms 20,904 KB
testcase_29	AC	89 ms 20,784 KB
testcase_30	AC	88 ms 20,876 KB
testcase_31	AC	88 ms 20,724 KB
testcase_32	AC	89 ms 20,796 KB
testcase_33	AC	93 ms 20,836 KB
testcase_34	AC	97 ms 20,920 KB
testcase_35	AC	95 ms 20,952 KB
testcase_36	AC	98 ms 20,820 KB
testcase_37	AC	98 ms 20,804 KB
testcase_38	AC	89 ms 20,716 KB
testcase_39	AC	90 ms 21,104 KB
testcase_40	AC	94 ms 20,756 KB
testcase_41	AC	93 ms 20,824 KB
testcase_42	AC	100 ms 21,048 KB
testcase_43	AC	92 ms 20,904 KB
testcase_44	AC	90 ms 20,716 KB
testcase_45	AC	90 ms 20,732 KB
testcase_46	AC	92 ms 20,816 KB
testcase_47	AC	93 ms 20,848 KB
testcase_48	AC	98 ms 20,860 KB
testcase_49	AC	93 ms 20,876 KB
testcase_50	AC	93 ms 21,192 KB
testcase_51	AC	99 ms 20,820 KB
testcase_52	AC	100 ms 20,880 KB
testcase_53	AC	128 ms 21,152 KB
testcase_54	AC	110 ms 20,800 KB
testcase_55	AC	126 ms 21,072 KB
testcase_56	AC	108 ms 20,992 KB
testcase_57	AC	128 ms 21,240 KB
testcase_58	AC	120 ms 20,924 KB
testcase_59	AC	145 ms 21,420 KB
testcase_60	AC	115 ms 21,228 KB
testcase_61	AC	146 ms 21,196 KB
testcase_62	AC	137 ms 21,156 KB
testcase_63	AC	94 ms 20,820 KB
testcase_64	AC	136 ms 21,132 KB
testcase_65	AC	106 ms 21,000 KB
testcase_66	AC	115 ms 21,036 KB
testcase_67	AC	124 ms 20,892 KB
testcase_68	AC	136 ms 21,212 KB
testcase_69	AC	136 ms 21,040 KB
testcase_70	AC	149 ms 21,132 KB
testcase_71	AC	139 ms 21,364 KB
testcase_72	AC	132 ms 21,152 KB
testcase_73	AC	155 ms 21,340 KB
testcase_74	AC	155 ms 21,312 KB
testcase_75	AC	155 ms 21,216 KB
testcase_76	AC	152 ms 21,104 KB
testcase_77	AC	156 ms 21,104 KB
testcase_78	AC	155 ms 21,100 KB
testcase_79	AC	152 ms 21,508 KB
testcase_80	AC	153 ms 21,104 KB
testcase_81	AC	154 ms 21,212 KB
testcase_82	AC	141 ms 21,104 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}
typedef complex<double> C;
const double PI=acos(-1.0);
vector<C> tmp;
size_t sz;
vector<C> fft(vector<C> a, bool inv=false){
    size_t mask=sz-1;
    size_t p=0;
    for(size_t i=sz>>1; i>0; i>>=1){
        auto& cur=((p&1) ? tmp : a);
        auto& nex=((p&1) ? a : tmp);
        C e=polar(1.0, 2*PI*i*(inv ? -1.0 : 1.0)/sz);
        C w=1;
        for(size_t j=0; j<sz; j+=i){
            for(size_t k=0; k<i; k++){
                nex[j+k]=cur[((j<<1)&mask)+k]+w*cur[(((j<<1)+i)&mask)+k];
            }
            w*=e;
        }
        p++;
    }
    if(p&1) swap(a, tmp);
    if(inv) for(size_t i=0; i<sz; i++) a[i]/=sz;
    return a;
}
vector<ll> convolute(vector<int> a, vector<int> b){
    size_t m=a.size()+b.size()-1;
    sz=1;
    while(sz<m) sz<<=1;
    tmp.resize(sz);
    vector<C> A(sz), B(sz);
    for(size_t i=0; i<a.size(); i++) A[i]=C{(double)a[i], 0};
    for(size_t i=0; i<b.size(); i++) B[i]=C{(double)b[i], 0};
    A=fft(A); B=fft(B);
    for(size_t i=0; i<sz; i++) A[i]*=B[i];
    A=fft(A, true);
    vector<ll> ans(m);
    for(size_t i=0; i<m; i++) ans[i]=round(A[i].real());
    return ans;
}
bool comp(P x, P y){
     return (double)y.second*log((double)y.first)-(double)x.second*log((double)x.first)+log((double)(y.first+y.second))-log((double)(x.first+x.second))>0;
}
int main()
{
    int n; cin>>n;
    int a[100010];
    vector<int> c(100001);
    for(int i=0; i<n; i++){
        cin>>a[i];
        c[a[i]]++;
    }
    ll s=1;
    ll p=0;
    for(int i=n-1; i>=0; i--){
        (s*=powmod(a[i], p))%=MOD;
        p+=a[i];
    }
    vector<ll> v=convolute(c, c);
    for(int i=0; i<n; i++){
        v[2*a[i]]--;
    }
    for(ll i=2; i<=200000; i++){
        v[i]/=2;
        (s*=powmod(i, v[i]))%=MOD;
    }
    int mn=a[n-1];
    P q[100010];
    for(int i=n-2; i>=0; i--){
        q[i]=P(a[i], mn);
        mn=min(mn, a[i]);
    }
    P p0=*min_element(q, q+n-1, comp);
    ll m=(p0.first+p0.second)*powmod(p0.first, p0.second)%MOD;
    (s*=inv(m))%=MOD;
    cout<<s<<endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード