
日记
不过,讨厌的事情就要早点做。 ——芙莉莲
上午
考逝。
私人考逝 私人题解
还是那句话:何谓私人?
这tm random_shuffle
都用上了?还有,这 hack
真的精心,连我的 都没卡掉。
T1
如题解所说:大水题,不讲。
T2
T3
尝试驯服模拟退火,但是失败了。
T4
没写。
中午
剪了个头
下午
改题。
我昨天有一道矩阵没改出来,看了 眼也没有看出来,于是直接ctj
T2
我们考虑每一条边的贡献。对于每条边,设它一端有 个点,另一端有 ,然后加一条限制: 。这样,我们会发现,枚举有 个点在 个点的一端,那么对于每一种情况,就会有 个点会走这条边过,并产生贡献(因为集合点必定是在点多的那一边)。而总共有 种情况,所以,我们就可以知道,对于每一条边,都有 的贡献。但是,我们看柿子里有一个烦人的 ,于是乎,我们就想着把这个柿子拆开,变成 ,但是,我们需要特判一下, 是不是偶数,如果是的,就得再加一个 。然后就是我看不懂的部分了。
总之,把代码贴在这里,以后总会懂的。
CPP
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
#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组。
想让我讲黑题是不可能的,你看我多菜啊。还是等着再练几个月,然后想起来再写吧。虽然可能永远想不起来
于是乎,颓废的一天就这么过完了。你会发现今天的日记我写的十分的潦草(啊我也觉得)。也许是我太累了,又或者是我鸽了 天的日记,不想写了,还是我天生不爱写日记呢?