伊埃斯的小站
日记

日记

Tue Dec 17 2024
8 分钟
life 日记
1089 字

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

上午 Link to 上午

考逝。

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

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

T1 Link to T1

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

T2 Link to T2

source

T3 Link to T3

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

T4 Link to T4

没写。

中午 Link to 中午

剪了个头

下午 Link to 下午

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

T2 Link to T2

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

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/extc++.h>
#define int long long
#define Inv(x) binpow(x,mod - 2)
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1000000007;
int n,m;
int head[maxn],idx = 1;
int siz[maxn];
struct edge
{
    int v,nxt;
    edge(int v = 0,int nxt = 0):v(v),nxt(nxt){};
}e[maxn << 1];
struct modint
{
    int val;
    modint(int x = 0):val(x % mod){};
    int &operator()(){return (val %= mod);}
    friend modint operator+(modint x,modint y){return ((x() + y()) % mod);}
    friend modint operator+=(modint &x,modint y){return x() = ((x() + y()) % mod);}
    friend modint operator-(modint x,modint y){return ((x() - y()) % mod + mod) % mod;}
    friend modint operator-=(modint &x,modint y){return x() = ((x() - y()) % mod + mod) % mod;}
    friend modint operator*(modint x,modint y){return (x() * y() % mod);}
    friend modint operator*=(modint &x,modint y){return x() = (x() * y() % mod);}
}fac[maxn],inv[maxn],ans,dp1[maxn],dp2[maxn];
void adde(int u,int v)
{
    e[++idx] = edge(v,head[u]);
    head[u] = idx;
}
modint binpow(modint x,int y)
{
    modint ret = 1;
    while (y)
    {
        if (y & 1)
            ret *= x;
        x *= x;
        y >>= 1;
    }
    return ret;
}
void init()
{
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= 1e6; i++)
    {
        fac[i] = fac[i - 1] * i;
        inv[i] = inv[i - 1] * Inv(i);
    }
}
modint c(int n,int m){return fac[n] * inv[n - m] * inv[m];}
void dfs(int u,int fa)
{
    siz[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        dfs(v,u);
        siz[u] += siz[v];
        ans += dp2[siz[v]];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    cin >> n >> m;
    int x;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        adde(i,x),adde(x,i);
    }
    if (n == 1)
    {
        cout << 0;
        return 0;
    }
    int k = (m - 1) >> 1;
    if (k < 1)
        dp1[1] = 0;
    else
        dp1[1] = c(n - 1,m - 1);
    for (int i = 2; i < n; i++)
        dp1[i] = dp1[i - 1] - c(i - 2,k - 1) * c(n - i,m - 1 - k);
    for (int i = 1; i < n; i++)
    {
        dp2[i] = i * dp1[i] + dp1[n - i] * (n - i);
        if (!(m & 1))
            dp2[i] += c(i,m >> 1) * c(n - i,m >> 1) * (m >> 1);
    }
    dfs(1,0);
    cout << ans();
    return 0;
}

T4 Link to T4

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

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


Telegram
Douban
Reddit
Pocket