hdu6595 Everything Is Generated In Equal Probability 數學期望

連結

        Everything Is Generated In Equal Probability

題意

        ①給個N(1≤N≤3000),在1~N中等機率取一個數n

        ②随機産生一個1~n的排列，記錄逆序對個數

        ③然後等機率随機取一個該排列的子序列

        ④再次記錄逆序對個數

        ⑤再次等機率去一個子序列……

        ⑥無窮遞歸下去，求逆序對總和的數學期望E(N)

        ⑦結果可能為分數，對998244353取模

思路

    樣例資訊挖掘

        先用兩層循環枚舉分子分母，結合快速幂取分母逆元，将N=2和N=3的答案還原成分數，分别為1/3和8/9

        N=1的時候,n隻能取1,排列隻有1，不存在數對，自然沒有逆序對

        假設N=x時答案為F(x)

        n=x的随機排列對答案的貢獻期望為f(x)

        算出f(2)和f(3)也沒有什麼用，我們找不到規律，但是等會兒推出來公式可以用它驗證公式的正确性。

    公式推導

       在長度為n的随機排列中，數對(x,y)有

個

       由于沒有相等元素，正序對(x,y) x<y 個數 == 逆序對(x,y) x>y個數

       逆序對期望為

          分裂産生的子序列共有

種,其中，長度為j的有

種

        則有：

                    本身期望       裂變期望

       裂變期望包含變為本身(子序列為本身)，移項将其消去得到遞推式：

        得到f(i)的遞推公式，帶入i=2和i=3，得到f(2)=2/3 f(3)=2，和我們之前的計算結果相同，故式子正确。

    解題方法

       我們可以在O(n^2)時間内根據遞推式求出每個f(i)

        并求出其字首和，這樣便可以通過

        在O(1)時間内解決每個詢問。

代碼

        太懶了，就貼個std吧

#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;
}
           

        至于O(1)公式(n^2-1)/9為什麼正确- -我不知道，反正我沒推出來，題解也沒說。