G.蚌埠住了

题解：

状态划分:

为前个数中，必选第个数组成的长度为k的非严格单调子序列方案数。

状态转移:

当选第个数组成的长度为的序列，它将有前面个长度为的转移而来。即：

，其中。

其世界复杂度为

线段树优化：

我们可以将，优化掉。

即将其放入权值线段树里，查询区间和。复杂度降为

标程：

#include <iostream>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=1e4+7;
const int S=1e5+1;
const ll mod=998244353;
int n,s,dp[N][101],tree[400001][101],a[N];
void update(int k,int l,int r,int p,int val,int up){
    tree[k][up]=(tree[k][up]+val)%mod;
    if(l==r) return ;
    if(p<=mid) update(lch,l,mid,p,val,up);
    else update(rch,mid+1,r,p,val,up);
}
int query(int k,int l,int r,int ql,int qr,int up){
    if(ql<=l&&r<=qr){
        return tree[k][up];
    }
    int sum1=0,sum2=0;
    if(ql<=mid) sum1=query(lch,l,mid,ql,qr,up);
    if(mid+1<=qr) sum2=query(rch,mid+1,r,ql,qr,up);
    return (sum1+sum2)%mod;
}
int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    update(1,1,S,1,1,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=s;j++){
            dp[i][j]=query(1,1,S,1,a[i],j-1)%mod;
        }
        for(int j=1;j<=s;j++){
            update(1,1,S,a[i],dp[i][j],j);
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+dp[i][s])%mod;
    }
    cout<<ans<<endl;
}