LibreOJ 2528 「ZJOI2018」树

发表于 | 分类于 |

stO EI Orz！
stO xYx Orz！

令无标号有根树构成的组合类为 \(\mathcal T\)，令其中的一个组合对象 \(\tau\) 作为等价类的大小为 \(s(\tau)\)，那么题意即是求 \[ \sum\limits_{\tau \in \mathcal T} s^k(t) \]

考虑两个等价类的笛卡尔积 \(\tau_1 \times \tau_2\)，则显然 \(|\tau_1 \times \tau_2| = |\tau_1| + |\tau_2|\) 且 \(s(\tau_1 \times \tau_2) = \binom{|\tau_1|+|\tau_2|}{|\tau_1|} s(\tau_1) s(\tau_2)\)。
因此考虑 GF \[ T(\mathcal T;x) = \sum\limits_{\tau \in \mathcal T} \frac{s^k(\tau) x^{|\tau|}}{|\tau|!^k} \]

其线性及积性均容易验证。

考虑分析 \(\mathcal T\) 的结构，这意味着我们需要考虑去除根再把剩下的部分视作 \({\rm MSET}(\mathcal T)\)。

注意这里我和 xyx 和 cmd 都犯过同一个错误：此处附加的因子 \(\frac1{|\tau|^k}\) 和本身的等价类大小并不能简单地通过经典的 MSET 构造结合。
因此结合无标号计数中的 MSET 构造和有标号计数中的 SET 构造，此处所应当使用的 MSET 构造应当形如 \[ T({\rm MSET}(\mathcal T)) = \prod\limits_{\tau \in \mathcal T} \sum\limits_{i\ge 0} \frac{s^{ik}(\tau) x^{i|\tau|}}{|\tau|^{ik} (i!)^k} \]

说到底，我们不能混淆组合对象的大小函数和等价类大小以及附加因子的关系。

记 \(\mathop{\rm xexp}x\) 为 \[ \sum\limits_{i\ge 0} \frac{x^i}{(i!)^k} \]

从而我们的 MSET 即为 \[ \prod\limits_{\tau \in \mathcal T} \mathop{\rm xexp}T(\tau) \]

可是 \(\mathop{\rm xexp}\) 并不保有线性到积性，因此不能像熟知的 \(\exp\) 一般直接写作 \(\exp T\)。
考虑直接使用 ln / exp 推导 \[ \exp \sum\limits_{\tau \in \mathcal T} \ln \circ \mathop{\rm xexp} T(\tau) \]

不过这样还是没有什么卵用。
考虑维护更多的信息，加入一元 \(u\)： \[ T(\mathcal T;x,u) = \sum\limits_{\tau \in \mathcal T} x^{|\tau|}\frac1{1-u\frac{s(\tau)}{|\tau|!}} \]

则乘法改为 \(x\) 元上的卷积，\(u\) 元上的点乘。
模仿原来的结果考虑重新定义 \({\rm MSET}\)，则 \[ [u^k] \mathop{\rm xexp} T(\tau) = \sum\limits_{i \ge 0} \frac{s^{ik}(\tau) x^{|\tau|i}}{(|\tau|!)^{ik} (i!)^k} \]

令 \[ F(x) = \ln \sum\limits_{i\ge 0} \frac{x^i}{(i!)^k} \]

那么 \[ [u^k] \ln \circ \mathop{\rm xexp}T(\mathcal \tau) = F\left(\frac{s^k(\tau) x^{|\tau|}}{(|\tau|!)^k}\right) \]

于是 \[ \begin{aligned} \sum\limits_{\tau \in \mathcal T} \ln \circ \mathop{\rm xexp} T(\tau) &= \sum\limits_{\tau \in \mathcal T} F\left(\frac{s^k(\tau) x^{|\tau|}}{(|\tau|!)^k}\right) \\ &= \sum\limits_{\tau \in \mathcal T} \sum\limits_{i\ge 1} f_i \left(\frac{s^k(\tau) x^{|\tau|}}{(|\tau|!)^k}\right)^i \\ &= \sum\limits_{i\ge 1} f_i \sum\limits_{\tau \in \mathcal T} \left(\frac{s^k(\tau) x^{|\tau|}}{(|\tau|!)^k}\right)^i \\ &= \sum\limits_{i\ge 1} f_i \sum\limits_{\tau \in \mathcal T} \frac{s^{ik}(\tau) x^{|\tau|i}}{(|\tau|!)^{ik}} \\ &= \sum\limits_{i\ge 1} f_i [u^{ik}] T(\mathcal T; x^i) \end{aligned} \]

因此 \[ {\rm DEL}(\mathcal T) = {\rm MSET}(\mathcal T) \]

于是 \[ T' = \exp \sum\limits_{i\ge 1} f_i [u^{ik}] T(\mathcal T; x^i) \]

（这个求导是一个形式化的记号，代表去除根，但并不符合真正的求导意义。）

关于这个怎么处理，考虑到 \[ \ln T' - [u^k] T = \sum\limits_{i\ge 2} f_i [u^{ik}] T(\mathcal T; x^i) \]

那么我们从大的 \(u\) 指标推到小的 \(u\) 指标，并且有用的 \(u\) 指标只有 \(k\) 的不超过 \(nk\) 的倍数。
当进入一个新的 \(k\)，使用 \(O(n^2)\) 的 ln 计算出 \(F\)，从而右式是容易直接调和级数复杂度处理的。
剩下的问题在于左式的处理，不过推出 \(O(n^2)\) 半在线的 exp 的式子之后会发现这同时也是容易半在线处理的。

处理左式和 \(F\) 的复杂度为 \[ \sum\limits_{k=1}^n O\left(\frac{n^2}{k^2}\right) = O(n^2) \]

这是著名的巴塞尔问题。

处理右式的复杂度为 \[ \sum\limits_{k=1}^n O\left(\frac nk \log \frac nk\right) = O(n \log^2 n) \]

因此总复杂度为 \(O(n^2)\)。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2e3;
int n,k,mod;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int inv[N + 5];
int pw[N + 5][N + 5],ipw[N + 5][N + 5];
int f[N + 5],g[N + 5];
int t[N + 5][N + 5],c[N + 5][N + 5];
int ans;
vector<int> d[N + 5];
int main()
{
    while(~scanf("%d%d%d",&n,&k,&mod))
    {
        memset(c,0,sizeof c),memset(t,0,sizeof t);
        inv[1] = 1;
        for(register int i = 2;i <= N;++i)
            inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
        for(register int i = 1;i <= n;++i)
            pw[1][i] = fpow(i,k),ipw[1][i] = fpow(pw[1][i],mod - 2);
        for(register int u = 2;u <= n;++u)
            for(register int i = 1;i <= n / u;++i)
                pw[u][i] = (long long)pw[u - 1][i] * pw[1][i] % mod,
                ipw[u][i] = (long long)ipw[u - 1][i] * ipw[1][i] % mod;
        for(register int i = 2;i <= n;++i)
            d[i].clear();
        for(register int i = 2;i <= n;++i)
            for(register int j = i;j <= n;j += i)
                d[j].push_back(i);
        for(register int u = n;u;--u)
        {
            g[0] = 1;
            for(register int i = 1;i <= n / u;++i)
                g[i] = (long long)g[i - 1] * ipw[u][i] % mod;
            for(register int i = 1;i <= n / u;++i)
            {
                f[i] = (long long)i * g[i] % mod;
                for(register int j = 0;j <= i - 2;++j)
                    f[i] = (f[i] - (long long)(j + 1) * f[j + 1] % mod * g[i - j - 1] % mod + mod) % mod;
                f[i] = (long long)f[i] * inv[i] % mod;
            }
            for(register int i = 1;i <= n / u;++i)
                for(int j : d[i])
                    c[u][i] = (c[u][i] + (long long)f[j] * t[u * j][i / j]) % mod;
            t[u][1] = 1;
            for(register int i = 1;i < n / u;++i)
            {
                for(register int j = 0;j <= i - 1;++j)
                    t[u][i + 1] = (t[u][i + 1] + (long long)(j + 1) * (t[u][j + 1] + c[u][j + 1]) % mod * pw[u][i - j] % mod * t[u][i - j]) % mod;
                t[u][i + 1] = (long long)t[u][i + 1] * inv[i] % mod * ipw[u][i + 1] % mod;
            }
        }
        ans = (long long)t[1][n] * fpow(n,k) % mod;
        printf("%d\n",ans);
    }
}