5318: Increasing Subsequence
内存限制：1024 MB
时间限制：15.000 S
评测方式：文本比较
命题人：
提交：11
解决：2
题目描述
Alice is playing a game with his friend Bob on a permutation P of length N. Two players take turns choosing numbers while Alice going first.
In each round, the player should pick an element in P that is larger than any element chosen by two players previously. Besides that, if one player picked P_i before, the element P_j he picks in this round should satisfy with j > i. If there are mutiple chooses, the player will randomly pick an element that satisfies all the conditions with equal probability.
In the first round, each player could choose an element in any position, but Bob should choose an element bigger than the first element chosen by Alice. The game ends immediately when a player couldn't find an appropriate element to pick.
Alice and Bob wonder what is the expected number of rounds. Here the expected number we calculate is the sum of steps of two players.
In each round, the pla
In the first round, each pla
Alice and Bob wonder what is the expected number of rounds. Here the expected number we calculate is the sum of steps of two pla
输入
The first line contains one integer N, describing the length of P.(1<=N<=5000)
The second line contains N integers P1...PN, describing permutation P.
The second line contains N integers P1...PN, describing permutation P.
输出
Output the answer in one line. If the expected number is A/B, print A*B^998244351 mod 998244353
样例输入 复制
3
1 2 3样例输出 复制
831870296