题解 P7986 [USACO21DEC] HILO P

· · 题解

先考虑暴力 DP。设 tot_{i,j,k,0/1} 表示已经放完了 i 个数，猜过的不大于 x 的最大数为 j，大于 x 的最大数为 k，上一次是 HI 还是 LO 的方案数，同理记 sum_{i,j,k,0/1} 表示 HILO 出现的次数总和，转移枚举填 [j+1,x],[x+1,k],[1,j-1] \cup [k+1,n] 三个区间中的哪一个即可做到 \mathcal{O}(n^4)，使用前缀和可以做到 \mathcal{O}(n^3)。

上面那个 DP 状态是 \mathcal{O}(n^3) 的，感觉没啥前途。计数题的另一个常用方法是贡献法，可以考虑一下。但是直接考虑满足 i \leq x,j \gt x 的 (i,j) 对答案的贡献也不是很好做，因为有可能在 j,i 之间会出现一个小于 i 的数提前 LO，那不妨直接考虑 j \gt x 的 j 的贡献。一个想法是枚举在 j 之前出现的小于等于 x 的最小数 i，那么现在 [1,i-1] 和 [j+1,n] 之内的数就不会产生任何影响，用一个排列数算一下系数之后，问题变成求满足 i 在 j 前且 j 之后第一个数在 [i+1,x] 之间的排列数，这个系数就是 (x-i) \times (j-i-2)!，而这个计算是可以 \mathcal{O}(1) 完成的，于是问题在 \mathcal{O}(n^2) 时间内得到解决。注意要特殊处理不存在小于等于 x 的数出现在 j 之前的情况。

实际上把式子写出来化简是可以做到 \mathcal{O}(n) 的，不过这个并不重要。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
const int maxn=5e3+5;
const int mod=1e9+7;
int inv[maxn],fact[maxn],finv[maxn];
void init(){
    inv[0]=inv[1]=fact[0]=fact[1]=finv[0]=finv[1]=1;
    for(int i=2;i<=maxn-2;i++){
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        fact[i]=1ll*fact[i-1]*i%mod;
        finv[i]=1ll*finv[i-1]*inv[i]%mod;
    }
    return;
}
int biga(int n,int k){return 1ll*fact[n]*finv[n-k]%mod;}
int n,x;
signed main(){
    init();
    scanf("%d%d",&n,&x);
    int ans=0;
    for(int j=x+1;j<=n;j++)for(int i=0;i<=x-1;i++){
        int ba=n-j,fr=std::max(0,i-1),p=x-i,q=j-x-1;
        (ans+=1ll*biga(n,ba+fr)*fact[p+q-1]%mod*p%mod)%=mod;
    }
    printf("%d",ans);
    return 0;
}
//namespace burningContract

感谢你的阅读。