F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 5161. -- 最长上升子序列

5161: 最长上升子序列

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 144  Solved: 98
[Submit][Status][Discuss]

Description

现在有一个长度为n的随机排列,求它的最长上升子序列长度的期望。
为了避免精度误差,你只需要输出答案模998244353的余数。

Input

输入只包含一个正整数n。N<=28

Output

输出只包含一个非负整数,表示答案模998244353的余数。
可以证明,答案一定为有理数,设其为a/b(a、b为互质的整数),你输出的整数为x,
则你需要保证0≤x<998244353且a与bx模998244353同余。

Sample Input

2

Sample Output

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

HINT

Source

By 徐明宽

[Submit][Status][Discuss]

HOME Back