题解：CF1874E Jellyfish and Hack

Graphcity · 2024-04-23 10:34:26 · 题解

注意到 fun(p) 的最大值仅有 \dfrac{n(n+1)}{2}，所以当 m 大于这个值时肯定无解。此时 m 的范围变成了 O(n^2) 级别。然后我们考虑转化问题，考虑 p 的逆排列 p'，fun(p) 的值就是 p' 的笛卡尔树上每个结点的子树大小之和。

设 f_{n,k} 表示长度为 n 的排列，权值为 k 的方案数。转移考虑枚举 1 所在的位置，然后将排列分成左右两半分开计算，最后再用组合数合并即可。朴素实现是 O(n^6) 的。

考虑优化。注意到 f_n 可以写成一个 O(n^2) 次的多项式，我们考虑代入这么多个点值，这样一次乘法就变成 O(n^2) 级别的了。最后我们再通过拉插把多项式还原出来，就可以得到答案。总时间复杂度 O(n^4)。常数很小，跑得很快。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=200,K=2.05e4,Mod=1e9+7;

inline int Pow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%Mod;
        x=1ll*x*x%Mod,y>>=1;
    }
    return res;
}

int n,m,ans,f[Maxn+5][K+5],val[K+5],g[K+5];
int C[Maxn+5][Maxn+5],fac[K+5],inv[K+5],iv[K+5];
inline int sgn(int x) {return (x&1)?Mod-1:1;}

int main()
{
    cin>>n>>m; if(m>K) {cout<<0<<endl; return 0;}
    C[0][0]=fac[0]=inv[0]=1; For(i,0,K) f[0][i]=1;
    For(i,1,K) fac[i]=1ll*fac[i-1]*i%Mod,iv[i]=Pow(i,Mod-2);
    inv[K]=Pow(fac[K],Mod-2); Rof(i,K-1,1) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
    For(i,1,n) {C[i][0]=1; For(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;}
    For(i,1,n)
    {
        For(j,1,i) For(k,0,K) f[i][k]=(f[i][k]+1ll*f[j-1][k]*f[i-j][k]%Mod*C[i-1][j-1])%Mod;
        For(j,0,K) f[i][j]=1ll*f[i][j]*Pow(j,i)%Mod;
    }
    For(i,0,K) val[i]=1ll*f[n][i]*inv[i]%Mod*inv[K-i]%Mod*sgn(K-i)%Mod;
    g[1]=1; For(i,1,K) Rof(j,i+1,1) g[j]=(1ll*g[j]*(Mod-i)+g[j-1])%Mod;
    For(i,m,K) ans=(ans+1ll*val[0]*g[i+1])%Mod;
    For(i,1,K)
    {
        For(j,1,K+1) g[j]=1ll*(g[j]-g[j-1]+Mod)*(Mod-iv[i])%Mod;
        For(j,m,K) ans=(ans+1ll*val[i]*g[j])%Mod;
        Rof(j,K+1,1) g[j]=(1ll*g[j]*(Mod-i)+g[j-1])%Mod;
    } cout<<ans<<endl;
    return 0;
}