Eous的小站
日记

日记

Tue Dec 17 2024
7 分钟
life 日记
987 字

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

上午#

考逝。

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

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

T1#

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

T2#

source

T3#

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

T4#

没写。

中午#

剪了个头

下午#

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

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#

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

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