日记 - 伊埃斯的博客站

不过，讨厌的事情就要早点做。 ——芙莉莲

上午

考逝。

私人考逝私人题解
还是那句话：何谓私人？

这tm random_shuffle 都用上了？还有，这 hack 真的精心，连我的 $\mathcal{O}(n^3)$ 都没卡掉。

T1

如题解所说：大水题，不讲。

T2

source

T3

尝试驯服模拟退火，但是失败了。

T4

没写。

中午

剪了个头

下午

改题。
我昨天有一道矩阵没改出来，看了 $1145141919810$ 眼也没有看出来，~~于是直接ctj~~

T2

我们考虑每一条边的贡献。对于每条边，设它一端有 $s$ 个点，另一端有 $n - s$ ，然后加一条限制： $s \le n - s$ 。这样，我们会发现，枚举有 $i$ 个点在 $s$ 个点的一端，那么对于每一种情况，就会有 $\min(i,m - i)$ 个点会走这条边过，并产生贡献（因为集合点必定是在点多的那一边）。而总共有 $\binom{s}{i} \times \binom{n - s}{m - i}$ 种情况，所以，我们就可以知道，对于每一条边，都有 $\sum\limits_{i = 1}^{m - 1}\binom{s}{i} \cdot \binom{n - s}{m - i} \cdot \min(i,m - i)$ 的贡献。但是，我们看柿子里有一个烦人的 $\min$ ，于是乎，我们就想着把这个柿子拆开，变成 $2 \times \sum\limits_{i = 1}^{\frac{m - 1}{2}}\binom{s}{i} \cdot \binom{n - s}{m - i} \cdot i$ ，但是，我们需要特判一下， $m$ 是不是偶数，如果是的，就得再加一个 $\binom{s}{\frac{m}{2}} \cdot \binom{n - s}{\frac{m}{2}} \cdot \frac{m}{2}$ 。然后就是我看不懂的部分了。
总之，把代码贴在这里，以后总会懂的。

1
#include<bits/extc++.h>
2
#define int long long
3
#define Inv(x) binpow(x,mod - 2)
4
using namespace std;
5
const int maxn = 1e6 + 5;
6
const int mod = 1000000007;
7
int n,m;
8
int head[maxn],idx = 1;
9
int siz[maxn];
10
struct edge
11
{
12
    int v,nxt;
13
    edge(int v = 0,int nxt = 0):v(v),nxt(nxt){};
14
}e[maxn << 1];
15
struct modint
16
{
17
    int val;
18
    modint(int x = 0):val(x % mod){};
19
    int &operator()(){return (val %= mod);}
20
    friend modint operator+(modint x,modint y){return ((x() + y()) % mod);}
21
    friend modint operator+=(modint &x,modint y){return x() = ((x() + y()) % mod);}
22
    friend modint operator-(modint x,modint y){return ((x() - y()) % mod + mod) % mod;}
23
    friend modint operator-=(modint &x,modint y){return x() = ((x() - y()) % mod + mod) % mod;}
24
    friend modint operator*(modint x,modint y){return (x() * y() % mod);}
25
    friend modint operator*=(modint &x,modint y){return x() = (x() * y() % mod);}
26
}fac[maxn],inv[maxn],ans,dp1[maxn],dp2[maxn];
27
void adde(int u,int v)
28
{
29
    e[++idx] = edge(v,head[u]);
30
    head[u] = idx;
31
}
32
modint binpow(modint x,int y)
33
{
34
    modint ret = 1;
35
    while (y)
36
    {
37
        if (y & 1)
38
            ret *= x;
39
        x *= x;
40
        y >>= 1;
41
    }
42
    return ret;
43
}
44
void init()
45
{
46
    fac[0] = inv[0] = 1;
47
    for (int i = 1; i <= 1e6; i++)
48
    {
49
        fac[i] = fac[i - 1] * i;
50
        inv[i] = inv[i - 1] * Inv(i);
51
    }
52
}
53
modint c(int n,int m){return fac[n] * inv[n - m] * inv[m];}
54
void dfs(int u,int fa)
55
{
56
    siz[u] = 1;
57
    for (int i = head[u]; i; i = e[i].nxt)
58
    {
59
        int v = e[i].v;
60
        if (v == fa)
61
            continue;
62
        dfs(v,u);
63
        siz[u] += siz[v];
64
        ans += dp2[siz[v]];
65
    }
66
}
67
signed main()
68
{
69
    ios::sync_with_stdio(0);
70
    cin.tie(0);
71
    cout.tie(0);
72
    init();
73
    cin >> n >> m;
74
    int x;
75
    for (int i = 2; i <= n; i++)
76
    {
77
        cin >> x;
78
        adde(i,x),adde(x,i);
79
    }
80
    if (n == 1)
81
    {
82
        cout << 0;
83
        return 0;
84
    }
85
    int k = (m - 1) >> 1;
86
    if (k < 1)
87
        dp1[1] = 0;
88
    else
89
        dp1[1] = c(n - 1,m - 1);
90
    for (int i = 2; i < n; i++)
91
        dp1[i] = dp1[i - 1] - c(i - 2,k - 1) * c(n - i,m - 1 - k);
92
    for (int i = 1; i < n; i++)
93
    {
94
        dp2[i] = i * dp1[i] + dp1[n - i] * (n - i);
95
        if (!(m & 1))
96
            dp2[i] += c(i,m >> 1) * c(n - i,m >> 1) * (m >> 1);
97
    }
98
    dfs(1,0);
99
    cout << ans();
100
    return 0;
101
}

T4

source
真·难度对标今年S组。
想让我讲黑题是不可能的，你看我多菜啊。还是等着再练几个月，然后想起来再写吧。~~虽然可能永远想不起来~~

于是乎，颓废的一天就这么过完了。你会发现今天的日记我写的十分的潦草（啊我也觉得）。也许是我太累了，又或者是我鸽了 $3$ 天的日记，不想写了，还是我天生不爱写日记呢？

Thanks for reading!

日记

周二 12月 17 2024

951 字 · 7 分钟

life 日记