出题人题解 | #无畏死灵术士莉莲娜与锁链面纱#

原题解链接：https://ac.nowcoder.com/discuss/150009

一个简单的期望$dpdp$。用std::vector与std::map暴力存下状态，$O(n)O(n)$ 转移。转移时枚举 选到了哪个数，根据后继状态更新当前状态。注意当前状态的后继有可能还是自己，那么只要移 一下项就可以计算了。

$f_{st}=p_1{f}_{nx{t}_1}+p_2{f}_{nx{t}_2}+\dots +p_k{f}_{st}f\_\{s\; t\}=p\_\{1\}\; f\_\{n\; x\; t\_\{1\}\}+p\_\{2\}\; f\_\{n\; x\; t\_\{2\}\}+\backslash ldots+p\_\{k\}\; f\_\{s\; t\}$

转移的式子是这样的，其中有Pe的概率转移到自身，那么我们整理可得:

$(1-p_k)f_{st}=p_1{f}_{nx{t}_1}+p_2{f}_{nx{t}_2}+\dots +p_{k-1}{f}_{nx{t}_{k-1}}\backslash left(1-p\_\{k\}\backslash right)\; f\_\{s\; t\}=p\_\{1\}\; f\_\{n\; x\; t\_\{1\}\}+p\_\{2\}\; f\_\{n\; x\; t\_\{2\}\}+\backslash ldots+p\_\{k-1\}\; f\_\{n\; x\; t\_\{k-1\}\}$

处理一下边界就可以了。至于状态数，我们考虑每一次操作之间顺序是不重要的。即先选到$aa$再选到$bb$和先选到$bb$再选到$aa$最终的状态是相同的。那么状态数就是$0(2^n)0(2^n)$的，可以通过此题。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
long long MOD = 998244353;
long long inv[30];
int n;
int b[30];
vector<int> a;
long long res[1 << 20];

long long power(long long b, long long p)
{
    long long t = b, res = 1;
    while (p)
    {
        if (p & 1) res = res * t % MOD;
        t = t * t % MOD;
        p >>= 1;
    }
    return res;
}
int main()
{
    for (int i = 1; i < 30; i ++) inv[i] = power(i, MOD - 2);
    cin >> n;
    for (int i = 0, k; i < n; i ++)
    {
        cin >> k;
        a.push_back(k);
        b[k] = i;
    }
    memset(res, -1, sizeof res);
    bool k = true;
    for (int i = 0; i < n && k; i ++)
        if (a[i] != i + 1) k = false;
    if (k)
    {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i < (1 << n); i ++)
    {
        int lst = -1;
        res[i] = 0;
        for (int j = 1; j <= n; j ++)
        {
            if (i & (1 << (j - 1))) lst = -1;
            else
            {
                if (b[j] < lst)
                {
                    res[i]  = - 1;
                    break;
                }
                lst = b[j];
            }
        }
    }
    for (int i = (1 << n) - 1; i >= 0; i --)
    if (res[i])
    {
        int t = 0;
        res[i] = n;
        for (int j = 0; j < n; j ++)
        {
            if (i & (1 << j)) t ++;
            else res[i] = (res[i] + res[i | (1 << j)]) % MOD;
        }
        res[i] = res[i] * inv[n - t] % MOD;
    }
    cout << res[0] << endl;
    return 0;
}