概率DP
Everything Is Generated In Equal Probability
Problem Description
One day, Y_UME got an integer $ N $ and an interesting program which is shown below:
Y_UME wants to play with this program. Firstly, he randomly generates an integer $n∈[1,N]$ in equal probability. And then he randomly generates a permutation of length $ n $ in equal probability. Afterwards, he runs the interesting program $(function calculate())$ with this permutation as a parameter and then gets a returning value. Please output the expectation of this value modulo $ 998244353$.
A permutation of length $n$ is an array of length $n$ consisting of integers only $∈[1,n]$ which are pairwise different.
An inversion pair in a permutation $p$ is a pair of indices $(i,j)$ such that $i>j$ and $ p_i < p_j $ . For example, a permutation $[4,1,3,2]$ contains 4 inversions: $(2,1),(3,1),(4,1),(4,3)$.
In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Note that empty subsequence is also a subsequence of original sequence.
Refer to here for better understanding.
Input
There are multiple test cases.
Each case starts with a line containing one integer $N(1≤N≤3000)$.
It is guaranteed that the sum of $N_s$ in all test cases is no larger than $5×10^4$.
Output
For each test case, output one line containing an integer denoting the answer.
Sample Input
1
2
3
Sample Output
0
332748118
554580197
Solution
在这里题目意思是给你一个数字 $N$ ,然后在 $ 1 \thicksim N $ 中随机生成一个数字$n$,将$ 1 \thicksim n $的所有的数进行随机排列,排列出一个数列,统计所有递归得到的子数列的逆序对数目之和的期望
例如,先给你一个数字$ N=2 $ , 那么$n$就有可能为$1$或者$2$,各有$\frac{1}{2}$的概率。如果是$1$,计算逆序对数目然后取子数列(只有空数列和它本身);如果是$2$,计算${1,2}$或者${2,1}$的逆序对(各有$\frac{1}{2}$的概率),然后取子数列(4个)并且计算逆序对的数目。我们随机选择一个数列作为原数列,然后计算该数列的逆序对数目,然后以该数列作为母数列,随机的得母数列的一个子数列,计算该子数列的逆序对数目,然后以该自数列作为母数列继续递归下去,直到得到数列长度为零,停止递归,返回逆序对总数的期望值并且对998244353求余。
对于 $N=2$ 的例子,详细的展示如下
有$\frac{1}{2}$的概率n=1,$\frac{1}{2}$的概率n=2.
若 $n=1$ ,则生成数列为$ \{1\} $ , 逆序对数目为 0 ,子数列有 其本身 $ \{1\} $ 和空数列$ \{\varnothing\} $
若 n=2 ,则随机生数列 $\{1,2\}$ 或者 $\{2,1\}$ ,计算逆序对数目。
如果生成 $\{1,2\}$,逆序对数目为$0$,生成子数列 $\{1\}$ , $\{2\}$ , $\{1,2\}$ 或者$\{\varnothing\}$空数列
如果生成 $\{2,1\}$,逆序对数目为$1$,生成子数列 $\{2\}$ , $\{1\}$ , $\{2,1\}$ 或者$\{\varnothing\}$空数列
所以答案是
取逆元,得 332748118
这是一个数学题,考虑一个长度为$N$的数列由$1 \thicksim N$ 组成(无相同元素),那么这个数列所含逆序对的数目的数学期望为$\frac{C_{N}^{2}}{2}$。因为每一对下标对于期望值的贡献为$\frac{1}{2}$,并且期望具有线性可加性。
则有:
也就是:
1 |
|