最长上升子序列

ID: 560

传统题

1000ms

512MiB

难度: 10

上传者:

标签>

BJWC2018 高级

说明

现在有一个长度为n的随机排列，求它的最长上升子序列长度的期望。

为了避免精度误差，你只需要输出答案模998244353的余数。

输入只包含一个正整数n。

对于 100%的数据，1≤n≤28。
共有 25组数据，对于第 i组数据（1≤i≤25）， n=i+3。

输出只包含一个非负整数，表示答案模998244353的余数。

可以证明，答案一定为有理数，设其为a/b（a、b为互质的整数），你输出的整数为x，

则你需要保证0≤x<998244353且a与bx模998244353同余。

499122178
【样例说明】
这是3/2。