提出 #53678772

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;

class opt_mint {
  public:
    operator bool() const{
        return v!=-1;
    }
    mint operator*() const{
        return mint::raw(v);
    }
    opt_mint& operator=(mint rhs){
        v=rhs.val();
        return *this;
    }
    opt_mint& operator+=(mint rhs){
        return *this=**this+rhs;
    }
  private:
    int v=-1;
};

mint solve(int a,int l,int r,int m,const vector<pair<int,int>>& lr,vector<opt_mint>& dp){
    if(a<0)
        return 1;
    const auto at=[&](int i,int j,int k)->opt_mint&{
        return dp[(i*(m+1)+j)*(m+1)+k];
    };
    auto& mem=at(a,l,r);
    if(mem)
        return *mem;
    auto [l0,r0]=lr[a];
    mem=0;
    if(l0==m){
        if(a==0)
            mem=r-l+1;
        else
            for(int i=l;i<=r;i++){
                mem+=solve(a-1,l,i,m,lr,dp);
                mem+=solve(a-1,i,r,m,lr,dp);
            }
    }else{
        for(int i=l;i<=l0;i++)
            mem+=solve(a-1,i,r,m,lr,dp);
        for(int i=r0;i<=r;i++)
            mem+=solve(a-1,l,i,m,lr,dp);
    }
    return *mem;
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(m);
    vector<int> inv(n,-1);
    for(int i=0;i<m;i++){
        cin>>a[i];
        inv[a[i]]=i;
    }
    vector<pair<int,int>> lr;
    int l=m,r=-1;
    for(int i=0;i<n;i++){
        int idx=inv[i];
        if(idx!=-1){
            l=min(l,idx);
            r=max(r,idx+1);
        }else{
            lr.emplace_back(l,r);
        }
    }
    int k=lr.size();
    vector<opt_mint> dp(k*(m+1)*(m+1));
    cout<<solve(k-1,0,m,m,lr,dp).val()<<'\n';
}

提出情報

ジャッジ結果