結果

問題 No.856 増える演算
ユーザー beetbeet
提出日時 2019-07-26 22:25:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 187 ms / 3,153 ms
コード長 7,978 bytes
コンパイル時間 3,174 ms
コンパイル使用メモリ 217,064 KB
実行使用メモリ 35,104 KB
最終ジャッジ日時 2023-09-15 02:13:52
合計ジャッジ時間 16,528 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 112 ms
27,508 KB
testcase_01 AC 113 ms
27,412 KB
testcase_02 AC 114 ms
27,520 KB
testcase_03 AC 113 ms
27,672 KB
testcase_04 AC 113 ms
27,580 KB
testcase_05 AC 112 ms
27,536 KB
testcase_06 AC 113 ms
27,680 KB
testcase_07 AC 114 ms
27,492 KB
testcase_08 AC 113 ms
27,520 KB
testcase_09 AC 112 ms
27,596 KB
testcase_10 AC 113 ms
27,480 KB
testcase_11 AC 115 ms
27,416 KB
testcase_12 AC 113 ms
27,492 KB
testcase_13 AC 113 ms
27,496 KB
testcase_14 AC 113 ms
27,408 KB
testcase_15 AC 114 ms
27,492 KB
testcase_16 AC 114 ms
27,620 KB
testcase_17 AC 113 ms
27,516 KB
testcase_18 AC 114 ms
27,500 KB
testcase_19 AC 113 ms
27,420 KB
testcase_20 AC 113 ms
27,480 KB
testcase_21 AC 112 ms
27,516 KB
testcase_22 AC 112 ms
27,412 KB
testcase_23 AC 115 ms
27,860 KB
testcase_24 AC 115 ms
27,936 KB
testcase_25 AC 113 ms
27,512 KB
testcase_26 AC 113 ms
27,440 KB
testcase_27 AC 113 ms
27,412 KB
testcase_28 AC 114 ms
28,084 KB
testcase_29 AC 114 ms
27,896 KB
testcase_30 AC 114 ms
27,676 KB
testcase_31 AC 114 ms
27,792 KB
testcase_32 AC 115 ms
28,160 KB
testcase_33 AC 118 ms
28,228 KB
testcase_34 AC 125 ms
29,608 KB
testcase_35 AC 126 ms
28,848 KB
testcase_36 AC 125 ms
29,304 KB
testcase_37 AC 123 ms
29,120 KB
testcase_38 AC 113 ms
27,756 KB
testcase_39 AC 116 ms
27,776 KB
testcase_40 AC 118 ms
27,944 KB
testcase_41 AC 116 ms
28,300 KB
testcase_42 AC 126 ms
29,736 KB
testcase_43 AC 118 ms
28,296 KB
testcase_44 AC 115 ms
27,516 KB
testcase_45 AC 114 ms
27,832 KB
testcase_46 AC 118 ms
28,284 KB
testcase_47 AC 117 ms
28,032 KB
testcase_48 AC 121 ms
28,840 KB
testcase_49 AC 117 ms
28,304 KB
testcase_50 AC 122 ms
29,132 KB
testcase_51 AC 125 ms
29,304 KB
testcase_52 AC 127 ms
29,620 KB
testcase_53 AC 159 ms
31,308 KB
testcase_54 AC 137 ms
29,000 KB
testcase_55 AC 158 ms
30,944 KB
testcase_56 AC 136 ms
28,836 KB
testcase_57 AC 161 ms
31,456 KB
testcase_58 AC 150 ms
30,424 KB
testcase_59 AC 174 ms
33,356 KB
testcase_60 AC 142 ms
29,376 KB
testcase_61 AC 177 ms
33,368 KB
testcase_62 AC 169 ms
32,768 KB
testcase_63 AC 116 ms
27,488 KB
testcase_64 AC 163 ms
32,016 KB
testcase_65 AC 129 ms
28,212 KB
testcase_66 AC 138 ms
29,264 KB
testcase_67 AC 149 ms
30,540 KB
testcase_68 AC 168 ms
32,788 KB
testcase_69 AC 165 ms
32,416 KB
testcase_70 AC 178 ms
34,380 KB
testcase_71 AC 168 ms
33,004 KB
testcase_72 AC 159 ms
31,624 KB
testcase_73 AC 184 ms
34,956 KB
testcase_74 AC 185 ms
34,936 KB
testcase_75 AC 185 ms
34,960 KB
testcase_76 AC 186 ms
34,936 KB
testcase_77 AC 185 ms
35,056 KB
testcase_78 AC 187 ms
35,036 KB
testcase_79 AC 184 ms
34,968 KB
testcase_80 AC 184 ms
35,028 KB
testcase_81 AC 185 ms
34,932 KB
testcase_82 AC 173 ms
35,104 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  // find x s.t. a^x = b
  static T log(T a,T b){
    const T sq=40000;
    unordered_map<T, T> dp;
    dp.reserve(sq);
    Mint res(1);
    for(int r=0;r<sq;r++){
      if(!dp.count(res.v)) dp[res.v]=r;
      res*=a;
    }
    Mint p=Mint(a).inv().pow(sq);
    res=b;
    for(int q=0;q<=MOD/sq+1;q++){
      if(dp.count(res.v)){
        T idx=q*sq+dp[res.v];
        if(idx>0) return idx;
      }
      res*=p;
    }
    assert(0);
    return T(-1);
  }

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}


constexpr int bmds(int x){
  const int v[] = {1012924417, 924844033, 998244353,
                   897581057, 645922817};
  return v[x];
}
constexpr int brts(int x){
  const int v[] = {5, 5, 3, 3, 3};
  return v[x];
}

template<int X>
struct NTT{
  static constexpr int md = bmds(X);
  static constexpr int rt = brts(X);

  inline int add(int a,int b){
    a+=b;
    if(a>=md) a-=md;
    return a;
  }

  inline int mul(int a,int b){
    return 1LL*a*b%md;
  }

  inline int pow(int a,int b){
    int res=1;
    while(b){
      if(b&1) res=mul(res,a);
      a=mul(a,a);
      b>>=1;
    }
    return res;
  }

  inline int inv(int x){
    return pow(x,md-2);
  }

  vector<vector<int> > rts,rrts;

  void ensure_base(int n){
    if((int)rts.size()>=n) return;
    rts.resize(n);rrts.resize(n);
    for(int i=1;i<n;i<<=1){
      if(!rts[i].empty()) continue;
      int w=pow(rt,(md-1)/(i<<1));
      int rw=inv(w);
      rts[i].resize(i);rrts[i].resize(i);
      rts[i][0]=1;rrts[i][0]=1;
      for(int k=1;k<i;k++){
        rts[i][k]=mul(rts[i][k-1],w);
        rrts[i][k]=mul(rrts[i][k-1],rw);
      }
    }
  }

  void ntt(vector<int> &a,bool f,int n=-1){
    if(n==-1) n=a.size();
    assert((n&(n-1))==0);

    for(int i=0,j=1;j+1<n;j++){
      for(int k=n>>1;k>(i^=k);k>>=1);
      if(i>j) swap(a[i],a[j]);
    }

    for(int i=1;i<n;i<<=1){
      for(int j=0;j<n;j+=i*2){
        for(int k=0;k<i;k++){
          int z=mul(a[i+j+k],f?rrts[i][k]:rts[i][k]);
          a[i+j+k]=add(a[j+k],md-z);
          a[j+k]=add(a[j+k],z);
        }
      }
    }

    if(f){
      int tmp=inv(n);
      for(int i=0;i<n;i++) a[i]=mul(a[i],tmp);
    }
  }

  vector<int> multiply(vector<int> as,vector<int> bs){
    int need=as.size()+bs.size()-1;
    int sz=1;
    while(sz<need) sz<<=1;
    ensure_base(sz);

    vector<int> f(sz),g(sz);
    for(int i=0;i<(int)as.size();i++) f[i]=as[i];
    for(int i=0;i<(int)bs.size();i++) g[i]=bs[i];
    ntt(f,0);ntt(g,0);
    for(int i=0;i<sz;i++) f[i]=mul(f[i],g[i]);
    ntt(f,1);

    f.resize(need);
    return f;
  }
};


namespace FFT{
  using dbl = long double;

  struct num{
    dbl x,y;
    num(){x=y=0;}
    num(dbl x,dbl y):x(x),y(y){}
  };

  inline num operator+(num a,num b){
    return num(a.x+b.x,a.y+b.y);
  }
  inline num operator-(num a,num b){
    return num(a.x-b.x,a.y-b.y);
  }
  inline num operator*(num a,num b){
    return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
  }
  inline num conj(num a){
    return num(a.x,-a.y);
  }

  int base=1;
  vector<num> rts={{0,0},{1,0}};
  vector<int> rev={0,1};

  const dbl PI=acosl(-1.0);

  void ensure_base(int nbase){
    if(nbase<=base) return;

    rev.resize(1<<nbase);
    for(int i=0;i<(1<<nbase);i++)
      rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1));

    rts.resize(1<<nbase);
    while(base<nbase){
      dbl angle=2*PI/(1<<(base+1));
      for(int i=1<<(base-1);i<(1<<base);i++){
        rts[i<<1]=rts[i];
        dbl angle_i=angle*(2*i+1-(1<<base));
        rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i));
      }
      base++;
    }
  }

  void fft(vector<num> &a,int n=-1){
    if(n==-1) n=a.size();
    assert((n&(n-1))==0);

    int zeros=__builtin_ctz(n);
    ensure_base(zeros);
    int shift=base-zeros;
    for(int i=0;i<n;i++)
      if(i<(rev[i]>>shift))
        swap(a[i],a[rev[i]>>shift]);

    for(int k=1;k<n;k<<=1){
      for(int i=0;i<n;i+=2*k){
        for(int j=0;j<k;j++){
          num z=a[i+j+k]*rts[j+k];
          a[i+j+k]=a[i+j]-z;
          a[i+j]=a[i+j]+z;
        }
      }
    }
  }

  vector<num> fa;

  vector<Int> multiply(vector<int> &a,vector<int> &b){
    int need=a.size()+b.size()-1;
    int nbase=0;
    while((1<<nbase)<need) nbase++;
    ensure_base(nbase);

    int sz=1<<nbase;
    if(sz>(int)fa.size()) fa.resize(sz);
    for(int i=0;i<sz;i++){
      int x=(i<(int)a.size()?a[i]:0);
      int y=(i<(int)b.size()?b[i]:0);
      fa[i]=num(x,y);
    }
    fft(fa,sz);

    num r(0,-0.25/sz);
    for(int i=0;i<=(sz>>1);i++){
      int j=(sz-i)&(sz-1);
      num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r;
      if(i!=j)
        fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r;
      fa[i]=z;
    }
    fft(fa,sz);

    vector<Int> res(need);
    for(int i=0;i<need;i++)
      res[i]=fa[i].x+0.5;

    return res;
  }

};


template<typename T>
struct SparseTable{
  using F = function<T(T,T)>;
  vector<vector<T> > dat;
  vector<int> ht;
  const F f;

  SparseTable(){}
  SparseTable(F f):f(f){}

  void build(const vector<T> &v){
    int n=v.size(),h=1;
    while((1<<h)<=n) h++;
    dat.assign(h,vector<T>(n));
    ht.assign(n+1,0);
    for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1;

    for(int j=0;j<n;j++) dat[0][j]=v[j];
    for(int i=1,p=1;i<h;i++,p<<=1)
      for(int j=0;j<n;j++)
        dat[i][j]=f(dat[i-1][j],dat[i-1][min(j+p,n-1)]);
  };

  T query(int a,int b){
    int l=b-a;
    return f(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]);
  }
};

//INSERT ABOVE HERE
signed main(){
  int n;
  cin>>n;
  vector<int> as(n);
  for(int i=0;i<n;i++) cin>>as[i];

  using M = Mint<int>;
  M ans{1};
  long long sum=0;
  for(int i=n-1;i>=0;i--){
    ans*=M(as[i]).pow(sum);
    sum+=as[i];
  }

  const int MAX = (1<<17)-1;
  vector<int> bs(MAX,0);
  for(int a:as) bs[a]++;
  auto cs=FFT::multiply(bs,bs);
  for(int a:as) cs[a+a]--;

  for(int i=0;i<(int)cs.size();i++)
    ans*=M(i).pow(cs[i]/2);

  auto f=[](int a,int b){return min(a,b);};
  SparseTable<int> sp(f);
  sp.build(as);

  using D = long double;
  vector<D> lg(MAX*2);
  for(int i=1;i<MAX*2;i++) lg[i]=log2((D)i);

  D val;
  M res;
  {
    int p=sp.query(0,1);
    int q=sp.query(1,n);
    val=lg[p+q]+lg[p]*(D)q;
    res=M(p+q)*M(p).pow(q);
  }

  for(int i=1;i<n;i++){
    int p=sp.query(0,i);
    int q=sp.query(i,n);
    D tmp=lg[p+q]+lg[p]*(D)q;
    if(tmp<val){
      val=tmp;
      res=M(p+q)*M(p).pow(q);
    }
  }

  ans/=res;
  cout<<ans<<endl;
  return 0;
}
0