LuoguP11900 不知道 题解

· · 题解

题目大意

给定一个长度为 k 数列 t，满足 t_0=1,t_i<t_{i+1},t_k\le n。

初始时有 n 个人站成一排。

然后进行 n-1 次操作，每次操作随机一个 i 满足位置 t_i 上有人，然后删掉这个人，并让后面的人补上来。

对于每个 i，问最后剩下的那个人是 i 的概率。

题目解法

经典地倒过来设，设 f_{i,j} 表示当前还有 i 个人，且最后剩下的是 j 的概率，那么转移有

f_{i,j}=\frac{\left(\sum_{p=0}^k[t_p<j]\right)f_{i-1,j-1}+\left(\sum_{p=0}^k[j<t_p\le i]\right)f_{i,j}}{\sum_{p=0}^k[t_p\le i]}

这样就可以做到 O(n^2) 了，接着考虑进一步优化。

分母上的数是固定的，可以最后再除。然后不妨设 a_i=\sum_{p=0}^k[t_p<i],b_i=\sum_{p=0}^k[t_p\le i]，那么得到

f_{i,j}=a_j\times f_{i-1,j-1}+(b_i-b_j)\times f_{i-1,j}

然后感觉这个转移式就很有规律，手模/打表一下就可以发现

f_{i,j}=\prod_{p=2}^ja_p\prod_{p=j+1}^i(b_p-b_1)

归纳证明也是容易的。

然后就可以容易的做到 O(n) 了。

主要代码如下：

int n, k, a[N], num[N], tmp[N];
ll comb = 1, f[N], pre[N], suf[N];

signed main()
{
    SetIO();
    cin >> n >> k;
    a[0] = 1;
    tmp[1] = 1;
    for (int i = 1; i <= k; i++)
        cin >> a[i], tmp[a[i]] = 1;
    for (int i = 1, j = 0; i <= n; i++)
    {
        num[i] = num[i - 1];
        while(j <= k && a[j] < i)
        {
            num[i]++;
            j++;
        }
        tmp[i] += num[i];
    }
    for (int i = 2; i <= n; i++)
        comb = comb *  Pow(tmp[i]) % MOD;
    pre[1] = 1;
    for (int i = 2; i <= n; i++)
        pre[i] = pre[i - 1] * num[i] % MOD;
    suf[n + 1] = 1;
    for (int i = n; i >= 1; i--)
        suf[i] = suf[i + 1] * (tmp[i] - tmp[1]) % MOD;
    for (int i = 1; i <= n; i++)
        cout << pre[i] * suf[i + 1] % MOD * comb % MOD << ' ';
    return 0;
}