P7986 [USACO21DEC] HILO P 题解

· · 题解

本篇文章翻译自官方题解。由于笔者考场上没有通过此题，如有不当之处，还请在评论区指出。

还有这里因该比 Gold 那题难不少吧，建议评紫(?。

Suppose that we have already constructed some prefix of the permutation, and there are j remaining non-redundant values below Bessie's number and k remaining non-redundant values above Bessie's number (we define non-redundant numbers as numbers that Elsie could guess that would give her more information). Also, consider the two cases where Bessie has most recently said either "HI" or "LO". Let b=0 be the case where Bessie has most recently said "LO" and let b=1 be the case where Bessie has most recently said "HI". Then, the expected number of "HILO"s for the original problem is just the case where j=x, k=N-x, b = 0.

考虑 dp 状态，假设我们已经算到了某个位置，并且剩余了 j 个有效的小于 x 的值和 k 个有效的大于 x 的值（在这里有效指之后还可以被猜到的数）。此时，我们令状态中的 b=0 若前一次是LO，b=1 若前一次是HI。这样的话，HILO出现的期望次数就是 j=x, k=N-x, b = 0 对应的状态。

Thus, it is sufficient to count the expected number of "HILO"s for each j \leq x, k \leq N-x, and b = 0 or b=1. Call this quantity dp[b][j][k]. Now, note that all redundant values do not affect the expected number of "HILOs", so we ignore all of them. Then, there are j+k possible values for the next number in the permutation, each of which occurs with probability \frac{1}{j+k}.

因而，我们只需对每个 j \leq x, k \leq N-x 计算HILO出现的期望次数。定义状态为 dp[b][j][k]。因为所有这些无效的数对答案都没有影响，所以说排列中的下一个数只有 j+k 种可能的值，每种数出现的概率都为 \frac{1}{j+k}。

We will first consider the case where b=0. Suppose that the next value in th.e permutation is less than x+0.5, of which there are j possibilities. Denote these values as v_0, v_1, v_2, \cdots v_{j-1} such that x+0.5 > v_0 > v_1 > v_2 \cdots > v_{j-1}.

首先考虑 b=0 的边界情况，假设排列中的下一个数是比 x+0.5 小的 j 种情况之一，记这样的数为 v_0, v_1, v_2, \cdots v_{j-1}，满足 x+0.5 > v_0 > v_1 > v_2 \cdots > v_{j-1}。

Suppose the next value in the permutation is v_{j_2} for some 0 \leq j_2 < j. Then, Bessie says "LO" (because v_{j_2} < x+0.5) and there are j_2 remaining nonredundant values below Bessie's number. The k initial nonredundant values above Bessie's number are still nonredundant, so the expected number of HILOs in the remaining sequence of values is dp[0][j_2][k].

设再往下的一个数为 v_{j_2} 且 0 \leq j_2 < j，那么 Bessie 将会说LO因为v_{j_2} < x+0.5），然后将会剩下 j_2 个有效的值小于 x ，而原本的 k 个大于 x 的有效的值将会保持不变，那期望下剩下的HILO的出现次数就是 dp[0][j_2][k]。

Similarly, if we consider the values greater than x+0.5, which we label x+0.5 < u_0 < u_1 < u_2 \cdots < u_{k-1}, if we choose one of these values u_{k_2}, Bessie says "HI" and there are k_2 remaining nonredundant values above Bessie's number, so the expected number of HILOs in the remaining sequence of values is dp[1][j][k_2].

相似地，如果我们考虑的值是比 x+0.5 大的，即 x+0.5 < u_0 < u_1 < u_2 \cdots < u_{k-1} 中的一个数 u_{k_2}，Bessie 就会说HI，并剩下 j_2 个有效的值大于于 x ，那期望下之后HILO的出现次数就是 dp[1][j_2][k]。

So, we have the recurrence dp[0][j][k] = \frac{\sum_{j_2 < j} dp[0][j_2][k] + \sum_{k_2 < k} dp[1][j][k_2]}{j+k}.

因此，我们得到转移方程 dp[0][j][k] = \frac{\sum_{j_2 < j} dp[0][j_2][k] + \sum_{k_2 < k} dp[1][j][k_2]}{j+k}。

For computing dp[1][j][k], we can apply the same technique. However, since Bessie has just said "HI", if we now choose a value v_{j_2} < x+0.5, Bessie will then say "LO" and the number of "HILO"s increases by one. We choose a value less than x+0.5 with probability \frac{j}{j+k}, so the expected number of "HILO"s increases by \frac{j}{j+k}.

在计算 dp[1][j][k] 时，我们可以使用相似的技巧。不过由于Bessie可能刚说了HI，如果我们现在选的数 v_{j_2} < x+0.5 则 Bessie 就会说LO那么HILO的出现次数就会加一。因为选一个小于 x+0.5 的值的概率为 \frac{j}{j+k}，所以HILO的期望出现次数会增加 \frac{j}{j+k}。

So, we have the recurrence dp[1][j][k] = \frac{\sum_{j_2 < j} dp[0][j_2][k] + \sum_{k_2 < k} dp[1][j][k_2]}{j+k} + \frac{j}{j+k}.

这样，我们得到转移方程 dp[1][j][k] = \dfrac{\sum_{j_2 < j} dp[0][j_2][k] + \sum_{k_2 < k} dp[1][j][k_2]}{j+k} + \frac{j}{j+k}。

Now, we can compute every value of dp[b][j][k] by iterating over all j_2 < j, k_2 < k and using the above recurrences. Since there are N^2 dp states and we sum over N smaller states, this leads to a time complexity of \mathcal{O}(N^3), which is enough for the first two subtasks.

至此，我们可以通过遍历一遍 j_2 < j, k_2 < k 来计算得到 dp[b][j][k] 。因为有 N^2 个状态，每次转移 \mathcal O(N)，因此我们得到一个时间复杂度 \mathcal{O}(N^3) 的算法，可以通过前两个 subtask。

To speed this up, note that the bottleneck of the runtime comes from computing the terms like \sum_{j_2 < j} dp[0][j_2][k]. Now, suppose we are computing the value dp[0][j][k] and want to find the value \sum_{j_2 < j} dp[0][j_2][k] without using a loop. To do this, note that we have already computed the value of dp[0][j-1][k], which required the value of \sum_{j_2 < j-1} dp[0][j_2][k]. Since we have already computed \sum_{j_2 < j-1} dp[0][j_2][k], we can use the fact that \sum_{j_2 < j} dp[0][j_2][k] = dp[0][j-1][k]+\sum_{j_2 < j-1} dp[0][j_2][k], which takes \mathcal O(1) time instead of \mathcal O(N) time to compute.

考虑优化转移，注意到算法的瓶颈在于计算像 \sum_{j_2 < j} dp[0][j_2][k] 的东西。我们计算 dp[0][j][k] 时希望不用遍历就得到 \sum_{j_2 < j} dp[0][j_2][k] 的值。注意到我们计算 dp[0][j-1][k] 时就已经用到 \sum_{j_2 < j-1} dp[0][j_2][k]，我们注意到 \sum_{j_2 < j} dp[0][j_2][k] = dp[0][j-1][k]+\sum_{j_2 < j-1} dp[0][j_2][k] 来把转移的时间复杂度由 \mathcal O(N) 优化到 \mathcal O(1)。

Since we can now compute the N^2 terms of the DP in \mathcal O(1) time each, our overall time complexity is now \mathcal{O}(N^2).

这样我们就可以以 \mathcal O(1) 复杂度计算 N^2 个状态，最终时间复杂度为 \mathcal{O}(N^2)，可以通过此题。

翻译到此结束，以下提供优质 500B 代码。


// Nothing is Given, Everything is Earned.
#include<bits/stdc++.h>
using namespace std;
using L=long long;
const int N=5.1e3,P=1e9+7;
int dp[2][N][N],sum1[N],sum0[N],inv[N];
int main()
{
    int n,x,y; cin>>n>>x; y=n-x;
    inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=1ll*(P-P/i)*inv[P%i]%P;
    for(int j=0;j<=x;j++)
        for(int k=0;k<=y;k++)
        {
            dp[0][j][k]=1ll*(sum1[j]+sum0[k])*inv[j+k]%P;
            dp[1][j][k]=1ll*(sum1[j]+sum0[k]+j)*inv[j+k]%P;
            (sum1[j]+=dp[1][j][k])%=P;
            (sum0[k]+=dp[0][j][k])%=P;
        }
    L ans=dp[0][x][y];
    for(L i=1;i<=n;i++) ans=1ll*ans*i%P;
    cout<<ans<<endl;
    return 0;
}