伊埃斯的小站
日记

日记

Wed Apr 02 2025
8 分钟
life 日记
1349 字

不计代价。

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

DFS Order 2 Link to

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

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

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

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

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

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

Core code:

CPP
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
\\ 预处理
int dfs1(int u,int fa)
{
    int res = 1;
    siz[u] = 1,tot[u] = 0;
    for (auto &v : g[u])
    {
        if (v == fa)
            continue;
        res = res * dfs1(v,u) % mod;
        siz[u] += siz[v],tot[u]++;
    }
    return res * fac[tot[u]] % mod;
}

\\ 转移
void dfs2(int u,int fa)
{
    memset(f,0,sizeof f);
    f[0][0] = 1;
    for (auto &v : g[u])
    {
        if (v == fa)
            continue;
        for (int i = tot[u]; i >= 1; i--)
            for (int j = siz[u]; j >= siz[v]; j--)
                f[i][j] = (f[i][j] + f[i - 1][j - siz[v]]) % mod;
    }
    for (auto &v : g[u])
    {
        if (v == fa)
            continue;
        for (int i = 1; i <= tot[u]; i++)
            for (int j = siz[v]; j <= siz[u]; j++)
                f[i][j] = (f[i][j] - f[i - 1][j - siz[v]] + mod) % mod;
        memset(tmp,0,sizeof tmp);
        for (int i = 0; i < tot[u]; i++)
            for (int j = 0; j <= siz[u]; j++)
                tmp[j + 1] = (tmp[j + 1] + fac[i] * fac[tot[u] - 1 - i] % mod * f[i][j] % mod) % mod;
        for (int i = 1; i <= n; i++)
            for (int j = 1; i + j <= n; j++)
                dp[v][i + j] = (dp[v][i + j] + dp[u][i] * tmp[j]) % mod;
        for (int i = tot[u]; i >= 1; i--)
            for (int j = siz[u]; j >= siz[v]; j--)
                f[i][j] = (f[i][j] + f[i - 1][j - siz[v]]) % mod;
    }
    for (auto v : g[u])
        if (v != fa)
            dfs2(v,u);
}

\\ 输出化简
for (int i = 1; i <= n; i++)
{
    int sum = 0;
    for (int j = 1; j <= n; j++)
        sum = (sum + dp[i][j]) % mod;
    int tmp = binpow(sum,mod - 2);
    for (int j = 1; j <= n; j++)
        printf("%lld%c",dp[i][j] * dp[1][1] % mod * tmp % mod," \n"[j == n]);
}

Great Expectations Link to

原题也做不起吗？

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

dpi,j=pi×dpi+1,j+tim+tim+{min⁡{dp0,0,dpi+1,j+di+tim+di+tim}j+di+n−ti<rdp0,0otherwise.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⁡\min 在那里镇着。我们考虑二分 dp0,0dp_{0,0}。如果最终的 dp0,0dp_{0,0} 比 midmid 小，就说明有些本该重开的我们选择了继续打，往小二分。反之往大二分。

糖果大战 Link to

高斯消元 yyds

游走 Link to

此游走非彼游走。

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

如果这题没模我不炸了？

汉堡 Burger Link to

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

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

后日谈 Link to 后日谈

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

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


Telegram
Douban
Reddit
Pocket