题意

问有多少个 $n$ 个点的完全图，满足所有边权在 $[1,K]$ 内，并且最小生成树只有一个。答案对质数 $p$ 取模。

$n \leq 50,K \leq 10^9,\max(n,K)+1 \leq p \leq 10^9$。

题解

先考虑如何求最小生成树：将所有边从小到大排序，按照顺序选择两个端点不在一个联通块的边，并合并这两个联通块。

所以我们可以考虑按照权值去考虑这些边：设 $f_{n,k}$ 表示考虑有 $n$ 个点的完全图，唯一的最小生成树的边权都 $\leq k$ 的方案数。

考虑如何转移：假设树上有边权为 $k$ 的边，我们删去这些在最小生成树上边权为 $k$ 的边，发现这个树一定分成了若干个联通块。联通块之间的边边权一定要 $>k$ 否则方案不唯一；然后就分解成了若干个子问题。

发现这个方案数和权值都和每个联通块的大小有关，所以我们考虑去做计数。先考虑一个暴力是枚举联通块的大小。为了防止计算重复，我们按顺序枚举：先枚举 $1$ 号点所在的联通块大小 $s_1$，再枚举剩下的点中最小权值的点所在的联通块大小 $s_2,s_3,\ldots,s_m$，这样可以得到选点方案数就是 $\binom{n-1}{s_1-1}\binom{n-s_1-1}{s_2-1}\ldots$。

接下来我们要计算生成树个数，这个题相当于就是每有一条连向大小为 $x$ 的块的边，对答案贡献就要乘上一个 $x$，根据经典的结论可以得到这样的方案数是 $(\sum s_i)^{m-2} \prod s_i = n^{m-2} \prod s_i$。

然后需要决定剩下的边的权值，每个都可以填 $(k,K]$ 中的任何一个数字，方案数是 $(K-k)^{\binom n 2 - \sum_{i=1}^m \binom {s_i}{2} - (m-1)}$。把这些东西乘起来就是这一个枚举对答案的贡献。

但是直接暴力显然不可行，我们考虑如何优化转移。这种优化显然是写成每次加入一个大小为 $x$ 的块，乘上的系数是和 $x$ 有强相关的式子的形式，所以可以写成：

$$ n^{-2}(K-k)^{\binom n 2 +1}\sum_{s_1,s_2,\ldots,s_m} \prod_{i=1}^m \binom{n-\sum_{j=1}^{i-1} s_j - 1}{s_i-1} s_i n (K-k)^{-(\binom {s_i} 2 + 1)} f_{s_i,k-1} $$

发现系数只需要知道之前的 $\sum s_i$ 就好了。这样每次转移可以再跑一个 dp：设 $g_i$ 表示已经 $\sum s_i = i$ 的系数和，转移枚举当前的联通块长度，乘上对应的权值即可。也就是

$$ g_i = \sum_{j=1}^i g_{i-j} \binom{n-(i-j)-1}{j-1} j n (K-k)^{-(\binom j 2 +1)} f_{j,k-1} $$

然后最后乘上外面那一堆东西就好了。复杂度 $O(n^3K)$。

这题 $K$ 很大，所以我们会去思考是否可以插值。打表发现 $f_n$ 关于 $k$ 是一个 $O(n^2)$ 项多项式，所以 $O(n^5)$ 求出点值然后写个插值就过了。需要稍微卡下常数，因为 tc 的机子并不快。。。

证明：设 $f_i$ 的次数是 $d_i$，根据最初的暴力式子可以得到：

$$ \begin{aligned} d_n &= \binom n 2 + 1 + \sum_i (d_{s_i}-\binom {s_i} 2 -1)\\ &= O(n^2) - \sum_i d_{s_i}-O(s_i^2) \end{aligned} $$

所以取 $d_i = O(i^2)$ 大概就能放过去。

代码

（代码内附赠一组我一开始跑的很慢的数据）

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 50 + 5;
const int MAXM = 2500 + 5;
int ha;

class UniqueMST{
private:
    int f[MAXN][MAXM];

    inline void add(int &x,int y){
        x += y-ha;x += x>>31&ha;
    }

    inline int qpow(int a,int n=ha-2){
        int res = 1;
        while(n){
            if(n & 1) res = 1ll*res*a%ha;
            a = 1ll*a*a%ha;
            n >>= 1;
        }
        return res;
    }

    // i 个点,j 个颜色
    int tmp[MAXN];
    int pw[MAXM];
    int C[MAXN][MAXN];
    int fac[MAXM],inv[MAXM];
    int pre[MAXM],suf[MAXM];

    inline int cha(int f[],int n,int x){
        pre[0] = suf[n+1] = 1;
        FOR(i,1,n) pre[i] = 1ll*pre[i-1]*(x-i+ha)%ha;
        ROF(i,n,1) suf[i] = 1ll*suf[i+1]*(x-i+ha)%ha;
        int ans = 0;
        FOR(i,1,n){
            int c = 1ll*pre[i-1]*suf[i+1]%ha*inv[i-1]%ha*inv[n-i]%ha*f[i]%ha;
            if((n-i)&1) c = (ha-c)%ha;
            add(ans,c);
        }
        return ans;
    }

public:
    int count(int N,int K,int m){
        ha = m;
        if(N == 2) return K%ha;
        int lim = std::min(MAXM-1,m-1);
        fac[0] = 1;FOR(i,1,lim) fac[i] = 1ll*fac[i-1]*i%ha;
        inv[lim] = qpow(fac[lim]);ROF(i,lim-1,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
        C[0][0] = 1;
        FOR(i,1,MAXN-1){
            C[i][0] = 1;
            FOR(j,1,i) C[i][j] = (C[i-1][j]+C[i-1][j-1])%ha;
        }
        FOR(k,1,std::min(K,N*N)) f[1][k] = 1,f[2][k] = k;f[1][0] = 1;
        // 特判 k == K: [n==2] 种
        FOR(n,3,N){
            int invn2 = 1ll*inv[n]*fac[n-1]%ha;
            invn2 = 1ll*invn2*invn2%ha;
            FOR(k,1,std::min(K,N*N)){
                int inv = qpow(K-k);CLR(tmp,0);
                pw[0] = 1;FOR(i,1,n) pw[i] = qpow(inv,i*(i-1)/2+1);
                tmp[0] = 1;
                FOR(i,1,n){
                    LL s = 0;
                    FOR(j,1,i){
                        s += 1ll*tmp[i-j]*j%ha*n%ha*f[j][k-1]%ha*pw[j]%ha*C[n-(i-j)-1][j-1]%ha;
                    }
                    tmp[i] = s%ha;
                }
                add(f[n][k],1ll*tmp[n]*qpow(K-k,n*(n-1)/2 + 1)%ha*invn2%ha);
            }
        }
        if(K <= N*N) return f[N][K-1];
        return cha(f[N],N*N,K);
    }
};

#ifdef RainAir
int main(){
    printf("%d\n",(new UniqueMST)->count(48,255871602,923853737));
    return 0;
}
#endif