最长上升子序列期望的两种巅峰解法：状压 DP 与杨表 RSK 对应

// 假设当前状态为 j，我们在第 k 个空位插入新数字
// 注意：最低位(bit 0)代表序列最左端，最高位代表序列最右端
pos = -1;
// 倒序遍历，其实是在从左到右扫描序列（寻找插入点右侧的第一个 1）
for (k = i - 1; ~k; k--) {
    // 构造新状态 t：
    // 1. (j >> k) << (k + 1) : 把 k 位及以上的位整体左移 1 位，腾出空隙
    // 2. (1 << k)            : 在第 k 位强行塞入一个 1 (新插入的最大值)
    // 3. (j & ((1 << k) - 1)): k 位以下的位保持原样
    t = ((j >> k) << (k + 1)) | (1 << k) | (j & ((1 << k) - 1));
  
    // 寻找右侧的 1: 因为低位在左，高位在右
    // pos 记录的是“当前遍历过的位置中，遇到的最近的 1”
    if (j & (1 << k)) pos = k; 
  
    // 如果右侧存在 1，将其翻转为 0
    if (~pos) t ^= (1 << (pos + 1)); 
  
    // 状态转移累加
    dp[now][t] = (dp[now][t] + dp[now ^ 1][j]) % mod;
}

/**
 * 洛谷 P4484 最长上升子序列的期望 (状态压缩 DP 解法)
 * * 【原书代码缺陷修复说明】：
 * 1. 内存溢出修复：原书 `ll dp[2][134217730]` 高达 2.14GB，在大部分 OJ 都会直接 MLE。
 * 实际上 N=24 时状态最多 2^24，且方案数取模后可用 int 存储。
 * 这里修改为 `int dp[2][1 << 24]`，内存骤降至 128MB。
 * 2. 移除重复计算：原书自己手写了 getlen 数组求二进制 1 的个数，
 * 这里替换为 GCC 内置的 `__builtin_popcount`，更优雅且省空间。
 * 3. 规范作用域与可读性：将原来堆在全局的 i, j, k 移入局部，
 * 并将反人类的 `~k` 还原为 `k >= 0`。
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;

// 快速幂求逆元 (原书的 my_pow)
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// DP 数组：滚动数组优化空间
// 1 << 24 刚好能过 N=24 的部分分数据 (128MB 内存)
// 如果强行跑 N=28，必须使用杨表解法，否则任何机器都会内存超限
int dp[2][1 << 24]; 

int main() {
    // 优化标准输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;
  
    // N-- 的原因是：第 1 个数插进去状态必定是 1，我们直接初始化掉，少一轮循环
    N--; 
  
    // 初始化：插入第 1 个数，差分数组状态为 0 (此时长度1，差分序列无元素，表现为0)
    dp[0][0] = 1; 

    int now = 1; // 滚动数组的当前维度

    // i 表示当前正在处理第 i+1 个插入的数字 (从小到大插入)
    for (int i = 1; i <= N; i++, now ^= 1) {
  
        // 每次进入新的一层，先清空当前层将要用到的状态空间
        // 状态上限为 1 << i，因为插入 i 个数最多产生 i 个差分位
        fill(dp[now], dp[now] + (1 << i), 0);
  
        // j 遍历上一层的所有合法状态
        for (int j = 0; j < (1 << (i - 1)); j++) {
            if (!dp[now ^ 1][j]) continue; // 剪枝：无方案数的状态直接跳过

            // ---------------------------------------------------------
            // 情况 1：新数字插在最前面 (对低位没有影响，直接整体左移)
            // ---------------------------------------------------------
            // 因为是从小到大插入，插在最前面意味着它比之前所有的数都大，
            // 且排在最前面。它自己构成一个长度为 1 的上升序列，
            // 并把后续的 LIS 整体往后推，所以末尾直接补 0 (j << 1)
            dp[now][j << 1] = (dp[now][j << 1] + dp[now ^ 1][j]) % MOD;

            // ---------------------------------------------------------
            // 情况 2：新数字插在序列中间或末尾
            // ---------------------------------------------------------
            int pos = -1; 
  
            // k 表示插入的空隙位置。从后往前倒着遍历 (k 从 i-1 到 0)
            // 为什么要倒着遍历？
            // 因为新插入一个上升点，会“消耗”掉它右侧(高位)的第一个上升点(即将 1 变成 0)。
            // 倒序遍历刚好能顺带记录遇到的上一个 1 的位置 (pos)。
            for (int k = i - 1; k >= 0; k--) {
  
                // 【核心位运算 1】：拆分并强行塞入 1
                // (j >> k) << (k + 1) : 把 k 位及以上的高位整体左移一位，腾出位置
                // (1 << k)            : 在第 k 位强行塞入一个 1 (新数字带来的 LIS 增长)
                // (j & ((1<<k)-1))    : 第 k 位以下的低位原封不动地拼接上去
                int t = ((j >> k) << (k + 1)) | (1 << k) | (j & ((1 << k) - 1));
  
                // 【核心位运算 2】：记录右侧(高位)最近的 1
                // 如果当前位 k 是 1，把它记下来。
                // 因为 k 是递减的，所以 pos 记录的永远是当前空隙右侧的、离得最近的 1 的位置。
                if (j & (1 << k)) pos = k;
  
                // 【核心位运算 3】：抹平潜能 (模拟 lower_bound 替换)
                // 如果右侧存在 1 (~pos 等价于 pos != -1)
                // 那么新插入的这个 1 会把原有的那个 1 替换掉（变为 0）。
                // 注意：在新的状态 t 中，原来的 pos 位已经被左移到了 pos+1，所以对 pos+1 取反
                if (pos != -1) t ^= (1 << (pos + 1)); 
  
                // 累加状态
                dp[now][t] = (dp[now][t] + dp[now ^ 1][j]) % MOD;
            }
        }
    }

    // N 轮循环结束后，答案存在 dp[now ^ 1] 中
    int final_state = now ^ 1;
    long long ans = 0;
    int max_S = 1 << N;

    // 统计所有最终状态对期望的贡献
    for (int i = 0; i < max_S; i++) {
        if (!dp[final_state][i]) continue;
  
        // __builtin_popcount 计算二进制中 1 的个数。
        // LIS 的实际长度 = 差分数组中 1 的个数 + 1 (即原本初始化的第 1 个数)
        int lis_len = __builtin_popcount(i) + 1;
  
        // 累加：当前状态的方案数 * 该状态的 LIS 长度
        ans = (ans + 1LL * dp[final_state][i] * lis_len) % MOD;
    }

    // 计算总期望 = 总和 / N! (等价于 乘上 N! 的逆元)
    long long fac = 1;
    for (int i = 1; i <= N + 1; i++) {
        fac = (fac * i) % MOD;
    }
  
    ans = (ans * power(fac, MOD - 2)) % MOD;

    cout << ans << "\n";

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;

// 快速幂求逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int n;
long long fact_n;
long long total_expected = 0;

// 计算当前整数划分的钩子并累加期望
void process_partition(const vector<int>& part) {
    int rows = part.size();
    if (rows == 0) return;
  
    int cols = part[0]; // 第一行长度，也就是该划分对应的 LIS 长度 lambda_1
    vector<int> col_len(cols, 0); // 记录每一列的长度
  
    // 预处理每列长度
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < part[i]; ++j) {
            col_len[j]++;
        }
    }

    // 计算分母：所有钩长平方的乘积
    long long prod_hook_sq = 1;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < part[i]; ++j) {
            // 钩长 = (该行右侧格子数) + (该列下方格子数) + 1 (自己)
            long long hook = (part[i] - 1 - j) + (col_len[j] - 1 - i) + 1;
            long long hook_sq = (hook * hook) % MOD;
            prod_hook_sq = (prod_hook_sq * hook_sq) % MOD;
        }
    }

    // 分子：n! * lambda_1
    long long term = (fact_n * cols) % MOD;
  
    // 当前划分对总期望的贡献：(n! * lambda_1) / 钩长平方积
    term = (term * modInverse(prod_hook_sq)) % MOD;
  
    total_expected = (total_expected + term) % MOD;
}

// DFS 枚举所有的整数划分
// rem: 剩余要划分的总和; max_val: 限制下一个选择的最大值以保证递减(形状合法)
void dfs(int rem, int max_val, vector<int>& part) {
    if (rem == 0) {
        process_partition(part);
        return;
    }
    for (int i = min(rem, max_val); i >= 1; --i) {
        part.push_back(i);
        dfs(rem - i, i, part);
        part.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (cin >> n) {
        // 预处理 N!
        fact_n = 1;
        for (int i = 1; i <= n; ++i) {
            fact_n = (fact_n * i) % MOD;
        }

        vector<int> part;
        dfs(n, n, part);

        cout << total_expected << "\n";
    }
    return 0;
}