P7986

快乐的大童 · 2023-10-04 19:43:28 · 题解

P7986 [USACO21DEC] HILO P

一种纯推式子的方法，不需要期望和 dp。

下面记原题的 x 为 k，原排列为 p。

修改了一些排版问题（）

O(n^5) solution

考虑计算每一对 HILO 对答案造成的贡献，发现一对 HILO 必定能由排列中的一对有序对 (x,y) 表示，其中 x>k,y\le k。

于是直接枚举 x,y 以及它们在排列中所在的位置 i,j，如果要让 (x,y) 产生贡献，必须要满足：

• 对于所有 1\le l<j,p_l >x 或者 p_l<y，记作条件 1。

这样才会使 x,y 不被跳过。

但这是不够的。考虑排列 1 5 2 3 4 6，在 k=3 的情况下，虽然 (5,3) 满足上述条件，但是并不会造成贡献。为了保证 (x,y) 能顺利配对造成贡献，我们还需要让 [i+1,j-1] 中每一个 <k 的数都被跳过，即让它们小于 [1,i) 中的最大的 <k 的数。设这个数为 z。

按照 z 的有无分类讨论：

• 若存在，对于每一个 x,y,i,j,z，答案即为 A_{n-x+z-1}^{j-3}\times (n-j)!\times (i-1)，表示在能选的所有数（即 [x+1,n],[1,z-1] 之间的所有数）之中选出一些数放在前 j-3 个位置上（前 j 个位置去掉已经钦定好了的 x,y,z）并随意排列，j 之后的数任意排列，z 可以放置在 [1,i-1] 的任意位置的方案数，其中 A 是排列数。
• 若不存在，对于每一个 x,y,i,j，答案即为 A_{n-x}^{j-2}\times(n-j)!，意义和存在的情况类似。

枚举 x,y,z,i,j 对上述答案求和即可，注意要让 z 满足条件 1，即 z<y。

通过第一个子任务。

void On5sol(){
    rep(i,2,n)rep(j,i+1,n)rep(x,k+1,n)rep(y,1,k)rep(z,1,y-1){
        ans=(ans+A(n-x+z-1,j-3)*fac[n-j]%mod*(i-1)%mod)%mod;
    }
    rep(i,1,n)rep(j,i+1,n)rep(x,k+1,n)rep(y,1,k){
        ans=(ans+A(n-x,j-2)*fac[n-j]%mod)%mod;
    }
}

O(n^4) solution

优化上述式子，发现答案式子与 y 无关，所以我们不再枚举 y，改为直接枚举 z，计算能对当前枚举的 z 造成贡献的 y 的数量。显然是 k-z，即 [z+1,k] 之间的所有 y。将原式乘以 k-z。

注意在不存在 z 的情况中，通过观察式子，发现每一个 y 都能对答案造成贡献，直接原式乘以 k。

通过第一个子任务。

void On4sol(){
    rep(i,2,n)rep(j,i+1,n)rep(x,k+1,n)rep(z,1,k){
        ans=(ans+A(n-x+z-1,j-3)*fac[n-j]%mod*(i-1)%mod*(k-z)%mod)%mod;
    }
    rep(i,1,n)rep(j,i+1,n)rep(x,k+1,n){
        ans=(ans+A(n-x,j-2)*fac[n-j]%mod*k%mod)%mod;
    }
}

O(n^3) solution

继续优化上述式子，以存在 z 的情况的答案式子为例，发现答案式子 \sum_{i=1}^n\sum_{j=i+1}^n\sum_{x=k+1}^n\sum_{z=1}^kA_{n-x+z-1}^{j-3}\times (n-j)!\times(i-1) 中， (n-j)!,(i-1) 均与 x,y 无关，将它们提出来，将答案式子化为 \sum_{i=1}^n(i-1)\sum_{j=i+1}^n(n-j)\sum_{x=k+1}^n\sum_{z=1}^kA_{n-x+z-1}^{j-3}，预处理每个 j 对应的 \sum_{x=k+1}^n\sum_{z=1}^kA_{n-x+z-1}^{j-3} 的值即可，记作 dp_j。统计答案时只需要枚举 i,j，将后面一大串式子代入成 dp_j 即可。

不存在 z 的情况同理，把这一部分优化成 O(n^2)。

预处理是 O(n^3) 的，统计是 O(n^2)。

虽然名字是 dp 但这个做法真的与 dp 无关

通过第一，二个子任务。

void On3sol(){
    rep(j,3,n)rep(x,k+1,n)rep(z,1,k)dp[j]=(dp[j]+A(n-x+z-1,j-3)*fac[n-j]%mod*(k-z)%mod)%mod;
    rep(i,2,n)rep(j,i+1,n)ans=(ans+(i-1)*dp[j]%mod)%mod;
    rep(j,2,n)rep(x,k+1,n)dp2[j]=(dp2[j]+A(n-x,j-2)*fac[n-j]%mod*k%mod)%mod;
    rep(i,1,n)rep(j,i+1,n)ans=(ans+dp2[j])%mod;
}

O(n^2) solution

仍然继续优化上述式子，发现计算的瓶颈是预处理，拎出预处理式子 dp_j=\sum_{x=k+1}^n\sum_{z=1}^kA_{n-x+z-1}^{j-3}，发现 \sum_{z=1}^kA_{n-x+z-1}^{j-3} 中 j-3 固定，n-x+z-1 是一段区间，前缀和优化掉即可。

通过第一、二、三个子任务。

void On2sol(){
    rep(j,3,n){
        int sum=0;s[0]=A(0,j-3);//注意A(0,j-3)也是可能有取值的
        rep(i,1,n)s[i]=(s[i-1]+A(i,j-3))%mod;
        rep(z,1,k)sum=(sum+(s[n-k+z-2]-(z==1?0:s[z-2])+mod)%mod*(k-z)%mod)%mod;
        dp[j]=sum*fac[n-j]%mod;
    }
    rep(i,2,n)rep(j,i+1,n)ans=(ans+(i-1)*dp[j]%mod)%mod;
    rep(j,2,n)rep(x,k+1,n)dp2[j]=(dp2[j]+A(n-x,j-2)*fac[n-j]%mod*k%mod)%mod;
    rep(i,1,n)rep(j,i+1,n)ans=(ans+dp2[j])%mod;
}