提出 #69962307

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define ll long long
#define mk make_pair
#define se second
#define fi first
#ifdef int
#define inf ((int)1e18+10)
#else
#define inf ((int)1e9+10)
#endif
//#define mid ((l+r)>>1)
//#define rs now<<1|1
//#define ls now<<1
using namespace std;
using namespace __gnu_pbds;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const double eps=1e-9;

inline int read(){
    int res=0,v=1;
    char c=getchar();
    while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
    while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
    return res*v;
}
template <int mod>
struct modint{

    int val;

    static int norm(const int &x){return x<0?x+mod:x;}
    static int Norm(const int &x){return x>=mod?x%mod:x;}

    modint inv()const{
        int a=val,b=mod,u=1,v=0,t;
        while(b>0)t=a/b,swap(a-=t*b,b),swap(u-=t*v,v);
        return modint(u);
    }


    modint():val(0){}
    modint(const int &m):val(norm(m)){}
    bool operator !()const{return !val;}
    modint(const long long &m):val(norm(m%mod)){}
    modint operator -()const{return modint(norm(-val));}
    bool operator ==(const modint &x){return val==x.val;}
    bool operator !=(const modint &x){return val!=x.val;}
    bool operator <=(const modint &x){return val<=x.val;}
    bool operator >=(const modint &x){return val>=x.val;}
    bool operator >(const modint &x){return val>x.val;}
    bool operator <(const modint &x){return val<x.val;}
    modint& operator *=(const modint &x){return val=static_cast<int>(1ll*val*x.val%mod),*this;}
    modint& operator <<=(const modint &x){return val=(1ll*val<<x.val)%mod,*this;}
    modint& operator +=(const modint &x){return val=Norm(1ll*val+x.val),*this;}
    modint& operator -=(const modint &x){return val=norm(1ll*val-x.val),*this;}
    modint& operator >>=(const modint &x){return val>>=x.val,*this;}
    modint& operator ^=(const modint &x){return val^=x.val,*this;}
    modint operator >>(const modint &x)const{return modint(*this)>>=x;}
    modint operator <<(const modint &x)const{return modint(*this)<<=x;}
    modint& operator /=(const modint &x){return *this*=x.inv();}
    modint operator +(const modint &x)const{return modint(*this)+=x;}
    modint operator -(const modint &x)const{return modint(*this)-=x;}
    modint operator *(const modint &x)const{return modint(*this)*=x;}
    modint operator /(const modint &x)const{return modint(*this)/=x;}
    modint operator ^(const modint &x)const{return modint(*this)^=x;}
    friend std::ostream& operator<<(std::ostream& os,const modint &a){return os<<a.val;}
    friend std::istream& operator>>(std::istream& is,modint &a){return is>>a.val;}
};
typedef modint<998244353>m98;

const int N=101;
cc_hash_table<ll,m98> dp[N<<1][N];
int Add=N*N;


pii a[Max];
int suma,sumb;
ll numa[Max],numb[Max];
int lasa[Max],lasb[Max];

bool chk(ll x,int id){return (x>=-numa[id]&&x<=numb[id]);}

bool Med;
signed main(){
    int n=read(),tot=0,x=read();
    ll val=x;
    for(int i=1;i<=n;++i){
        int x=read();
        val+=x;
        val-=i-1;
        a[++tot]=mk(i-1,0);
        a[++tot]=mk(x,1);
    }
    dp[0][0][0]=1;
    sort(a+1,a+1+tot);numa[tot+1]=numb[tot+1]=x;
    for(int i=tot;i>=0;--i){
        numa[i]=numa[i+1];lasa[i]=lasa[i+1];
        numb[i]=numb[i+1];lasb[i]=lasb[i+1];
        if(a[i].se)numa[i]+=a[i].fi,lasa[i]++;
        else numb[i]+=a[i].fi,lasb[i]++;
    }
    for(int i=1;i<=tot;++i){
        int z=a[i].fi;
        if(a[i].se){
            ++suma;
            for(int j=n-lasa[i-1]-lasb[i-1];j<=min(sumb,suma-1);++j){
                for(auto [k,val]:dp[i-1][j]){
                    if(chk(k,i))
                    dp[i][j][k]+=val;//向后匹配
                    if(chk(k+z,i))
                    dp[i][j+1][k+z]+=val*(sumb-j);
                }
            }
        }else{
            ++sumb;
            for(int j=n-lasa[i-1]-lasb[i-1];j<=min(sumb-1,suma);++j){
                for(auto [k,val]:dp[i-1][j]){
                    if(chk(k-z,i))
                    dp[i][j][k-z]+=val;
                    if(chk(k,i))
                    dp[i][j+1][k]+=val*(suma-j);
                }
            }
        }
    }
    m98 ans=0;
    for(auto [k,val]:dp[tot][n]){if(k<=x)ans+=val;}
    cout << ans << '\n';


    cerr<< "Time: "<<clock()/1000.0 << "s\n";
    cerr<< "Memory: " << abs(&Mst-&Med)/1000000.0 << "MB\n";
    return 0;
}
/*
排列 P 的代价为 \sum_{i=1}^n max(a_{P_i}-i+1,0);
求出 n! 中排列的代价中小于等于 X 的数量，这玩意确定不是线头dp？
按照权值拆分成位置和权值，设 dp[i][j][x] 表示考虑了前 i 位，权值匹配了 j 组的代价之和。
*/

提出情報

ジャッジ結果