日记 - 伊埃斯的博客站

不计代价。

~~不过我要是真的能做到 不计代价 的学习的话，我就不会那么菜了。~~

DFS Order 2↗

我们想到，一个子树内的 dfs 序肯定是连续的，我们考虑跑一个背包。设 $dp_{u,i}$ 表示 $u$ 在第 $i$ 个被访问的方案数。我们先想总共有多少个 dfs 序。那么显然，如果有 $tot_u$ 个子树，那么就有 $tot_u !$ 个子树排列的方式。每个子树又有自己的排列方式，乘起来就是了。 $dp_{1,1}$ 就是总的排列方式数。初始化就完了。

考虑如何转移：我们想从 $dp_{u,i} \to dp_{v,j}$ 。我们发现，一次加的肯定是一整个子树。那么我们想：做背包！设 $tmp_j$ 表示两个点在 dfs 序上相距 $j$ 的方案数。转移有显然的 $dp_{v,j} \leftarrow dp_{u,i} + tmp_{j - i}$ 。

但是我们发现：子树之间是不分顺序的，我们转移 $v$ 的时候还得扣掉 $v$ 的子树。我们不可能对于每个子树都做个不考虑它的背包，那么复杂度直奔 $O(n^4)$ ，显然不可取。

我们想：效仿淀粉质！每次扣掉 $v$ 的子树所做的贡献，转移完再加回来。我们在每个 $u$ 的子树转移时设单独的 $f_{i,j}$ 。表示在 $i$ 个子树内总共选了 $j$ 个点的方案数。那么初始化有 $f_{0,0} = 1$ 。转移有显然的 $f_{i,j} \leftarrow f_{i - 1,j - siz_v}$ 。

那么我们又如何从 $f \to tmp \to dp$ 呢？对于 $f \to tmp$ ，有 $tmp_{j + 1} = f_{i,j} \times i! \times (tot_u - i - 1)!$ ，三项分别表示 $i$ 个子树内的方案数， $i$ 个儿子排列的方案数，剩下儿子排列的方案数。

但是我们输出发现：比例正确，值错误。我们~~直接化到最简~~。我们发现比例正确但是值不正确的原因是有 $tmp_i$ ，~~所以就是直接化到最简~~。

Core code:

1
\\ 预处理
2
int dfs1(int u,int fa)
3
{
4
    int res = 1;
5
    siz[u] = 1,tot[u] = 0;
6
    for (auto &v : g[u])
7
    {
8
        if (v == fa)
9
            continue;
10
        res = res * dfs1(v,u) % mod;
11
        siz[u] += siz[v],tot[u]++;
12
    }
13
    return res * fac[tot[u]] % mod;
14
}
15

16
\\ 转移
17
void dfs2(int u,int fa)
18
{
19
    memset(f,0,sizeof f);
20
    f[0][0] = 1;
21
    for (auto &v : g[u])
22
    {
23
        if (v == fa)
24
            continue;
25
        for (int i = tot[u]; i >= 1; i--)
26
            for (int j = siz[u]; j >= siz[v]; j--)
27
                f[i][j] = (f[i][j] + f[i - 1][j - siz[v]]) % mod;
28
    }
29
    for (auto &v : g[u])
30
    {
31
        if (v == fa)
32
            continue;
33
        for (int i = 1; i <= tot[u]; i++)
34
            for (int j = siz[v]; j <= siz[u]; j++)
35
                f[i][j] = (f[i][j] - f[i - 1][j - siz[v]] + mod) % mod;
36
        memset(tmp,0,sizeof tmp);
37
        for (int i = 0; i < tot[u]; i++)
38
            for (int j = 0; j <= siz[u]; j++)
39
                tmp[j + 1] = (tmp[j + 1] + fac[i] * fac[tot[u] - 1 - i] % mod * f[i][j] % mod) % mod;
40
        for (int i = 1; i <= n; i++)
41
            for (int j = 1; i + j <= n; j++)
42
                dp[v][i + j] = (dp[v][i + j] + dp[u][i] * tmp[j]) % mod;
43
        for (int i = tot[u]; i >= 1; i--)
44
            for (int j = siz[u]; j >= siz[v]; j--)
45
                f[i][j] = (f[i][j] + f[i - 1][j - siz[v]]) % mod;
46
    }
47
    for (auto v : g[u])
48
        if (v != fa)
49
            dfs2(v,u);
50
}
51

52
\\ 输出化简
53
for (int i = 1; i <= n; i++)
54
{
55
    int sum = 0;
56
    for (int j = 1; j <= n; j++)
57
        sum = (sum + dp[i][j]) % mod;
58
    int tmp = binpow(sum,mod - 2);
59
    for (int j = 1; j <= n; j++)
60
        printf("%lld%c",dp[i][j] * dp[1][1] % mod * tmp % mod," \n"[j == n]);
61
}

Great Expectations↗

原题也做不起吗？

我们考虑 ~~ctj~~ 设 $dp_{i,j}$ 表示在 $i$ 个困难之后花费了 $j$ 分钟的方案数。那么有转移：

dp_{i,j} = p_i \times dp_{i + 1,j + tim} + tim + \\ \begin{cases} \min\{dp_{0,0},dp_{i + 1,j + d_i + tim} + d_i + tim\} & j + d_i + n - t_i < r\\ dp_{0,0} & \text{otherwise.} \end{cases}

具体来讲，就是如果还有可能破纪录，就尝试能不能破纪录。反之直接重开。但是我们发现这玩意有后效性，~~直接高斯消元~~。高斯消元肯定是不可取的，毕竟有个 $\min$ 在那里镇着。我们考虑二分 $dp_{0,0}$ 。如果最终的 $dp_{0,0}$ 比 $mid$ 小，就说明有些本该重开的我们选择了继续打，往小二分。反之往大二分。

游走↗

此游走非彼游走。

设总共有 $cnt$ 条路径，总长为 $len$ 。那么直接 dfs 搜出每个以每个点为起点的路径数量和路程总长，一加一除就出来了。

如果这题没模我不炸了？

汉堡 Burger↗

题意简化：有一个 01 串，0 的数量和 1 的数量各占一半。且最后的两个是连续的 1，求出这么滴的概率。

正难则反。设 $ans_i$ 为长度为 $i$ 的不成立的概率。那么显然有 $\displaystyle ans_n = \frac{\binom{n - 2}{\frac{n}{2} - 1}}{2^{n - 2}}$ 。我们发现这题没模，不能预处理阶乘。考虑推式子。推得 $ans_i = ans_{i - 2} \times \frac{i - 1}{i}$ 。答案就是 $1 - ans_n$ 。

后日谈

我都写 Java 了我还管常数吗？

好想念小学时无忧无虑的周末啊。。。

Thanks for reading!

日记

周三 4月 02 2025

1259 字 · 7 分钟

life 日记

日记

DFS Order 2↗

Great Expectations↗

糖果大战↗

游走↗

汉堡 Burger↗

后日谈

日记