题解：P13757 【MX-X17-T6】Selection

· · 题解

考虑对于 A>B 的限制进行容斥，改成 A\ge B 减去 A=B。对 A\ge B 计数是容易的，只需要 \max L_i\leq \min R_i。不妨设前 k 行是最终的 S，那么一定有 \forall x\in S,y\notin S,a_x\ne a_y，因此直接乘上 \binom{n}{k} 即可。但是这样很容易数重复，因此考虑容斥。枚举 p\in[1,k],q\in[1,n-k]，钦定第一部分中的 p 行与第二部分中的 q 行完全相等。不难发现此时被钦定相等的部分必须是 \max L 且是 \min R。取出某一个维，那么对于未被钦定的 n-k-q 行的 \max=x，k-p 行的 \min=y，此时这一维必须在 [x,y] 中，这是容易描述的，(p,q) 贡献就是 (\sum i^{n-k-q}(v-i+1)^{k-p})^m\binom{k}{p}\binom{n-k}{q}(-1)^{p+q+1}。

瓶颈在于给定 v 对于所有 x,y\leq n 预处理 \sum_{1\leq i<v} i^x(v-i)^y。直接做没什么性质因此考虑递推，令 g_{x,y}=\sum i^x(v-i)^y，通过拉格朗日插值（自然数幂和）可以处理出 x=0\vee y=0 的情况。另一方面，i^x(v-i)^{y+1}=vi^x(v-i)^y-i^{x+1}(v-i)^y，因此有递推 g_{x,y+1}=vg_{x,y}-g_{x+1,y}。拉格朗日插值一步需要做到线性，求逆可以每次类似于求阶乘逆的手法。结合快速幂，总时间复杂度 \mathcal O(n^2\log m)。

int calc(int m,int k){
// 返回 \sum_{1<=i<=m} i^k
}
void init(int n,int v){
    F(x,0,n)g[x][0]=(x==0)?(v-1):calc(v-1,x);
    F(j,0,n-1)F(i,0,n-j-1)g[i][j+1]=sub(1ll*v*g[i][j]%mod,g[i+1][j]);
}
void solve(){
    cin>>n>>m>>k>>v;
    F(i,0,n)C[i][0]=1;
    F(i,1,n)F(j,1,i)C[i][j]=add(C[i-1][j],C[i-1][j-1]);
    init(n,v);
    int sum=sub(0,g[n-k][k]);
    init(n,v+1);
    inc(sum,g[n-k][k]);
    int ans=qpow(sum,m);
    F(p,1,k)F(q,1,n-k){
        int val=1ll*C[k][p]*C[n-k][q]%mod*qpow(g[n-k-q][k-p],m)%mod;
        if((p+q)&1)inc(ans,val);
        else dec(ans,val);
    }
    ans=1ll*ans*C[n][k]%mod;
    cout<<ans<<'\n';
}