一道不知名的题

数学 题解

---

这题超级没有素质。

连个题解都搜不到。

好不容易会做一点。

测了一下没过样例。

不过还好我有办法。

先容大块再斥小块。

三百的三次方飘过。

得到CE优异成绩。

哇哈哈哈哈哈哈哈。

原来是因为OJ炸了。

我已经会放过我了。

接下来该放代码了。

做法描述在代码前。

题意:

$n$ 个点 每个点有一种颜色 问你 $n$ 个点构成的无根树中 不存在一个大于 $m$ 的同色的连通块

solution

容斥好题

我们考虑可以钦定几个点构成连通块然后再钦定同色块内不允许

我们考虑怎么计算答案 显然有一个结论:

$$ans=n^{m-2}\prod_{i=1}^m a_i$$
上式也就是 $n$ 个点分成 $m$ 个连通块最后连成树的方案数

考虑后面的东西可以怎么计算显然是在统计块内答案的时候一起做了

设计这样一个 $dp$ : $dp_{i,j}$ 表示前 $i$ 种颜色的点 分成 $j$ 个集合 集合内的方案数和大小的乘积

显然有:

$$dp_{i,j}=\sum_{k=0}^{min\{t_i,j\}} dp_{i-1,j-k}g_{t_i,k}$$
其中我们希望的 $g_{i,j}$ 表示 $i$ 个同色点分成 $j$ 个块的 块内方案数乘上 大小 的结果

先考虑每个钦定的连通块内的方案数,$f_{i,j}$ 表示将 $i$ 个点分成 $j$ 个大小小于等于 $m$ 的连通块的方案数 也就是不考虑块间连边的方案数:

$$f_{i,j}=\sum_{k=1}^{min\{i,m\}}k^{k-2}k{i - 1\choose k - 1}f_{i-k,j-1}$$
这个含义很绕口但是式子很显然

我们再可以考虑把不合法的情况容斥掉去掉 那么我们变钦定大小为 $i$ 同色的结点构成的集合内分成的 $j$ 个连通块 枚举块之间连同色边的数量 然后乘上容斥系数 $-1$ 再顺便算乘上块的大小的积

$$g_{i,j}=\sum_{k=1}^ik{i - 1\choose k - 1}g_{i - k,j - 1}\sum_{l=1}^k(-1)^{l-1}k^{l-2}f_{k,l}$$
字面意思 字面意思

预处理后面那个 $\sum$ 然后就可以 $\mathcal O(n^3)$ 预处理出来 $f,g$ 了

signed main()
{
    inv[1] = 1;
    for (int i = 2; i < N; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % mod,ifac[i] = ifac[i - 1] * inv[i] % mod;
    read(n,m);
    for (int i = 1; i <= n; i++)
    {
        int x;
        read(x);
        t[x]++;
    }
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            for (int k = 1; k <= i && k <= m; k++)
                f[i][j] = (f[i][j] + ksm(k,k - 2) * k % mod * C(i - 1,k - 1) % mod * f[i - k][j - 1] % mod) % mod;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j & 1) sum[i] = (sum[i] + f[i][j] * ksm(i,j - 1) % mod) % mod;
            else sum[i] = (sum[i] - f[i][j] * ksm(i,j - 1) % mod + mod) % mod;
        }
    }
    g[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            for (int k = 1; k <= i; k++)
                g[i][j] = (g[i][j] + C(i - 1,k - 1) * g[i - k][j - 1] % mod * sum[k] % mod) % mod;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 0; k <= t[i] && k <= j; k++)
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k] * g[t[i]][k] % mod) % mod;
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + dp[n][i] * ksm(n,i - 2) % mod) % mod;
    writeln(ans);
    return 0;
}