不需要高位前缀和的暴力

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

typedef long long ll;
typedef pair<int, int> pii;

const int N = 25, M = 3e3 + 5, mod = 998244353;

int C[M][N], b[N];

void add(int &a, int b) {
    a += b;
    if(a > mod) a -= mod;
}

void init(int n, int m) {
    C[0][0] = 1;
    for(int i=1; i<=n; i++) {
        C[i][0] = 1;
        for(int j=1; j<=min(i, m); j++) {
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            if(C[i][j] > mod) C[i][j] -= mod;
        }
    }
}

int dp[N][(1<<20)+5];
//有哪些位置填了数字，当前填到相对i大

int main() {
    freopen("easy.in", "r", stdin);
    freopen("easy.out", "w", stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    init(m, n);
    for(int i=1; i<=n; i++)
        cin >> b[i];

    dp[0][0] = 1;
    for(int i=1; i<=n; i++) {
        for(int S=0; S<(1<<n); S++) {
            int Inv = ((1<<n)-1) ^ S;
            for(int V=Inv; V>0; V=(V-1)&Inv) {
                int mx = 0;
                bool f = true;
                for(int j=1; j<=n; j++) {
                    if(S >> (j - 1) & 1) {
                        mx = max(mx, b[j]);
                    } else if(V >> (j - 1) & 1) {
                        f &= (mx + 1 == b[j]);
                    }
                }
                if(f) {
                    add(dp[i][S | V], dp[i-1][S]);
                }
            }
        }
    }
    int ans = 0;
    for(int i=1; i<=n; i++) {
        add(ans, 1LL * dp[i][(1 << n) - 1] * C[m][i] % mod);
    }
    cout << ans << "\n";
    return 0;
}

高维前缀和太难了

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

typedef long long ll;
typedef pair<int, int> pii;

const int N = 25, M = 3e3 + 5, mod = 998244353, NN = (1 << 20) + 5;

int C[M][N], b[N];

void add(int &a, int b) {
    a += b;
    if(a > mod) a -= mod;
}

void init(int n, int m) { //预处理组合数
    C[0][0] = 1;
    for(int i=1; i<=n; i++) {
        C[i][0] = 1;
        for(int j=1; j<=min(i, m); j++) {
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            if(C[i][j] > mod) C[i][j] -= mod;
        }
    }
}

int dp[N][NN];
//有哪些位置填了数字，当前填到相对i大

int pre[N][NN];
//预处理集合S到了位置i的前缀最长上升子序列

int main() {
    freopen("easy.in", "r", stdin);
    freopen("easy.out", "w", stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    init(m, n);
    for(int i=1; i<=n; i++)
        cin >> b[i];

    for(int S=0; S<(1<<n); S++) { //预处理前缀LIS
        int mx = 0;
        for(int i=1; i<=n; i++) {
            if(S >> (i - 1) & 1) mx = max(mx, b[i]);
            pre[i][S] = mx;
        }
    }

    dp[0][0] = 1;
    for(int i=1; i<=n; i++) { //先枚举第几层
        for(int j=n; j>=1; j--) { //从后往前填，因为不知道1是同层还是不同层，会影响前缀LIS
            for(int S=0; S<(1<<n); S++) { //枚举集合
                if(!(S >> (j - 1) & 1)) continue;
                int T = S ^ (1 << (j - 1)); //之前集合
                if(pre[j][T] + 1 == b[j]) { //合法填法
                    add(dp[i][S], dp[i-1][T]); //当前颜色填完了，跨层
                    add(dp[i][S], dp[i][T]); //当前颜色继续填，不跨层，相当于用单点加描述集合加
                }
            }
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++) { //由于枚举相对大小，给每个大小分配一个值域中对应数即可
        add(ans, 1LL * dp[i][(1 << n) - 1] * C[m][i] % mod);
    }
    cout << ans << "\n";
    return 0;
}

//我得看一下高维前缀和了TAT