Submission #20151898


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

using Int = long long;
const char newl = '\n';

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> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}


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;}

  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);
  using M = Mint<int, md>;
  vector< vector<M> > 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;
      M w=M(rt).pow((md-1)/(i<<1));
      M rw=w.inv();
      rts[i].resize(i);rrts[i].resize(i);
      rts[i][0]=M(1);rrts[i][0]=M(1);
      for(int k=1;k<i;k++){
        rts[i][k]=rts[i][k-1]*w;
        rrts[i][k]=rrts[i][k-1]*rw;
      }
    }
  }

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

    for(int i=0,j=1;j+1<n;j++){
      for(int k=n>>1;k>(i^=k);k>>=1);
      if(i>j) swap(as[i],as[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++){
          M z=as[i+j+k]*(f?rrts[i][k]:rts[i][k]);
          as[i+j+k]=as[j+k]-z;
          as[j+k]+=z;
        }
      }
    }

    if(f){
      M tmp=M(n).inv();
      for(int i=0;i<n;i++) as[i]*=tmp;
    }
  }

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

    ntt(as,0);ntt(bs,0);
    for(int i=0;i<sz;i++) as[i]*=bs[i];
    ntt(as,1);

    as.resize(need);
    return as;
  }

  vector<int> multiply(vector<int> as,vector<int> bs){
    vector<M> am(as.size()),bm(bs.size());
    for(int i=0;i<(int)am.size();i++) am[i]=M(as[i]);
    for(int i=0;i<(int)bm.size();i++) bm[i]=M(bs[i]);
    vector<M> cm=multiply(am,bm);
    vector<int> cs(cm.size());
    for(int i=0;i<(int)cs.size();i++) cs[i]=cm[i].v;
    return cs;
  }
};
template<int X> constexpr int NTT<X>::md;
template<int X> constexpr int NTT<X>::rt;


template<typename M_>
class Enumeration{
  using M = M_;
protected:
  static vector<M> fact,finv,invs;
public:
  static void init(int n){
    n=min<decltype(M::mod)>(n,M::mod-1);

    int m=fact.size();
    if(n<m) return;

    fact.resize(n+1,1);
    finv.resize(n+1,1);
    invs.resize(n+1,1);

    if(m==0) m=1;
    for(int i=m;i<=n;i++) fact[i]=fact[i-1]*M(i);
    finv[n]=M(1)/fact[n];
    for(int i=n;i>=m;i--) finv[i-1]=finv[i]*M(i);
    for(int i=m;i<=n;i++) invs[i]=finv[i]*fact[i-1];
  }

  static M Fact(int n){
    init(n);
    return fact[n];
  }
  static M Finv(int n){
    init(n);
    return finv[n];
  }
  static M Invs(int n){
    init(n);
    return invs[n];
  }

  static M C(int n,int k){
    if(n<k or k<0) return M(0);
    init(n);
    return fact[n]*finv[n-k]*finv[k];
  }

  static M P(int n,int k){
    if(n<k or k<0) return M(0);
    init(n);
    return fact[n]*finv[n-k];
  }

  // put n identical balls into k distinct boxes
  static M H(int n,int k){
    if(n<0 or k<0) return M(0);
    if(!n and !k) return M(1);
    init(n+k);
    return C(n+k-1,n);
  }
};
template<typename M>
vector<M> Enumeration<M>::fact=vector<M>();
template<typename M>
vector<M> Enumeration<M>::finv=vector<M>();
template<typename M>
vector<M> Enumeration<M>::invs=vector<M>();

//INSERT ABOVE HERE
const int MAX = 3030;
int ok[MAX][MAX]={};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;

  auto as=read(n);
  // vector<int> as(n);
  // iota(as.begin(),as.end(),1);

  for(int l=0;l<n;l++){
    // ok[l][r] represents [l, r)
    ok[l][l]=1;
    int p=0;
    for(int j=l;j<n;j++){
      if(p>=as[j]) break;
      ok[l][j+1]=1;
      p=as[j];
    }
  }
  ok[n][n]=1;

  NTT<2> ntt;
  using M = decltype(ntt)::M;
  using E = Enumeration<M>;
  E::init(1e6);

  M ans{0};

  vector<M> fs(m+1,0);
  for(int i=1;i<=m;i++) fs[i]=E::Finv(i);

  vector<M> dp(fs);
  for(int w=n-1;w>=0;w--){
    int v=n-w; // x + y
    if(m-v<0) break;

    // cout<<w<<":"<<dp[m]<<endl;
    M res=dp[m]*E::Fact(m)*E::Finv(v);
    res*=M(2).pow(m-v); // front or back

    for(int l=0;l+w<=n;l++){
      int r=l+w;
      int x=l,y=n-r;
      if(!ok[l][r]) continue;
      // cout<<l<<' '<<r<<":"<<res<<' '<<E::C(x+y,x)<<endl;
      ans+=res*E::C(x+y,x);
    }
    // cout<<w<<":"<<ans*E::Fact(m)<<endl;
    dp=ntt.multiply(dp,fs);
    dp.resize(m+1);
  }

  cout<<ans<<newl;
  return 0;
}

Submission Info

Submission Time
Task E - Cigar Box
User beet
Language C++ (GCC 9.2.1)
Score 700
Code Size 6325 Byte
Status AC
Exec Time 1938 ms
Memory 43336 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 36
Set Name Test Cases
Sample sample.txt, sample_2.txt, sample_3.txt
All dec_1097_1362.txt, dec_1214_138.txt, dec_2404_801.txt, dec_2886_2657.txt, dec_754_2194.txt, inc_2393_1050.txt, inc_2728_537.txt, inc_325_982.txt, inc_728_2645.txt, inc_786_1704.txt, random_102_2522.txt, random_1326_1061.txt, random_1421_916.txt, random_146_5.txt, random_1559_262.txt, random_16_157.txt, random_1775_2266.txt, random_2015_811.txt, random_20_1776.txt, random_222_41.txt, random_27_10.txt, random_2993_1514.txt, random_2_4.txt, random_333_1061.txt, random_360_208.txt, random_4_23.txt, random_501_2539.txt, random_781_1616.txt, random_7_203.txt, random_89_890.txt, sample.txt, sample_2.txt, sample_3.txt, sorted_3000_1.txt, sorted_3000_300.txt, sorted_3000_3000.txt
Case Name Status Exec Time Memory
dec_1097_1362.txt AC 349 ms 19700 KB
dec_1214_138.txt AC 35 ms 19900 KB
dec_2404_801.txt AC 146 ms 24932 KB
dec_2886_2657.txt AC 1655 ms 27220 KB
dec_754_2194.txt AC 487 ms 18664 KB
inc_2393_1050.txt AC 336 ms 28200 KB
inc_2728_537.txt AC 112 ms 31868 KB
inc_325_982.txt AC 73 ms 16660 KB
inc_728_2645.txt AC 474 ms 19232 KB
inc_786_1704.txt AC 260 ms 19732 KB
random_102_2522.txt AC 90 ms 15872 KB
random_1326_1061.txt AC 336 ms 20784 KB
random_1421_916.txt AC 155 ms 20852 KB
random_146_5.txt AC 26 ms 15596 KB
random_1559_262.txt AC 52 ms 21332 KB
random_16_157.txt AC 27 ms 14912 KB
random_1775_2266.txt AC 1107 ms 22792 KB
random_2015_811.txt AC 139 ms 23220 KB
random_20_1776.txt AC 37 ms 15376 KB
random_222_41.txt AC 34 ms 15696 KB
random_27_10.txt AC 28 ms 14912 KB
random_2993_1514.txt AC 468 ms 27356 KB
random_2_4.txt AC 28 ms 14868 KB
random_333_1061.txt AC 127 ms 16720 KB
random_360_208.txt AC 36 ms 16420 KB
random_4_23.txt AC 31 ms 15084 KB
random_501_2539.txt AC 335 ms 17544 KB
random_781_1616.txt AC 252 ms 18428 KB
random_7_203.txt AC 29 ms 14908 KB
random_89_890.txt AC 37 ms 15496 KB
sample.txt AC 32 ms 15016 KB
sample_2.txt AC 25 ms 15084 KB
sample_3.txt AC 36 ms 15624 KB
sorted_3000_1.txt AC 43 ms 42384 KB
sorted_3000_300.txt AC 65 ms 42804 KB
sorted_3000_3000.txt AC 1938 ms 43336 KB