HDOJ_Multi_school Day 2 T5

2019-07-28

概率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\} $

$f(1)=\frac{1}{2}·(f(1)+0) + \frac{1}{2}·f(\varnothing)\\ f(1)=0$

若 n=2 ，则随机生数列 $\{1,2\}$ 或者 $\{2,1\}$ ，计算逆序对数目。

如果生成 $\{1,2\}$，逆序对数目为$0$，生成子数列 $\{1\}$ , $\{2\}$ , $\{1,2\}$ 或者$\{\varnothing\}$空数列

$f(1,2)=\frac{1}{4}·(f(1)+0) + \frac{1}{4}·(f(2)+0) +\frac{1}{4}·(f(1,2)+0)+\frac{1}{4}·f(\varnothing)\\ f(1,2)=0$

如果生成 $\{2,1\}$,逆序对数目为$1$，生成子数列 $\{2\}$ , $\{1\}$ , $\{2,1\}$ 或者$\{\varnothing\}$空数列

$f(2,1)=\frac{1}{4}·(f(2)+0) + \frac{1}{4}·(f(1)+0) +\frac{1}{4}·(f(2,1)+1)+\frac{1}{4}·f(\varnothing)\\ f(2,1)=\frac{1}{3}$

所以答案是

$ans = \frac{1}{2}\left((f(1)+0) + \frac{1}{2}(f(1,2)+0) + \frac{1}{2}(f(2,1)+1)\right)= \frac{1}{3}$

取逆元，得 332748118

这是一个数学题，考虑一个长度为$N$的数列由$1 \thicksim N$ 组成（无相同元素），那么这个数列所含逆序对的数目的数学期望为$\frac{C_{N}^{2}}{2}$。因为每一对下标对于期望值的贡献为$\frac{1}{2}$，并且期望具有线性可加性。

则有：

$f(i) = \frac{1}{2^i} \sum_{j=0}^{i} C_{i}^{j}·f(j)$

也就是：

$f(i) = \frac{1}{2^i-1} \sum_{j=0}^{i-1} C_{i}^{j}·f(j)$ $ans(n) = \frac{1}{n} \sum_{i=1}{n}·f(i)$

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b) - 1; i >= (a); --i)
#define dd(a) cout << #a << " = " << a << " " 
#define de(a) cout << #a << " = " << a << endl
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pw(a) (1ll << (a))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;

const int N = 3030, P = 998244353;

inline int add(int a, int b) {
    if((a += b) >= P) a -= P;
    return a;
}
inline int mul(int a, int b) {
    return 1ll * a * b % P;
}
inline int kpow(int a, int b) {
    int r = 1;
    while(b) {
        if(b & 1) r = r * 1ll * a % P;
        a = a * 1ll * a % P;
        b >>= 1;
    }
    return r;
}

int n, f[N], C[N][N], pw[N];

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    rep(i, 0, N) C[i][0] = C[i][i] = 1;
    rep(i, 1, N) rep(j, 1, i) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);
    pw[0] = 1;
    rep(i, 1, N) pw[i] = pw[i - 1] * 2ll % P;
    rep(i, 2, N) {
        f[i] = mul(mul(i, i - 1), pw[i - 2]);
        rep(j, 0, i) f[i] = add(f[i], mul(C[i][j], f[j]));
        f[i] = mul(f[i], kpow(pw[i] - 1, P - 2));
    }
    while(cin >> n) {
        int ans = 0;
        rep(i, 1, n + 1) ans = add(ans, f[i]);
        ans = mul(ans, kpow(n, P - 2));
        cout << ans << endl;
    }
    return 0;
}