Codeforces 1097G. Vladislav and a Great Legend

当时不会做

题意

给定一棵 $n$ 个点的树

对于每个非空的点集 $X\subseteq {1,2,\dotsc,n}$，定义 $f(X)$ 表示最少的能让点集 $X$ 联通的边的数量

求

$$
\sum_{X\subseteq {1,2,\dotsc,n},X\ne \varnothing} (f(X))^k
$$

模 $10^9+7$

$n\le 10^5,k\le 200$

UOJ #269

题意

给定 $m$ 次函数 $f$ 和 $n,a$，求

$$
\sum_{k = 0}^{n}f(k)\binom{n}{k}a^k(1 - a) ^{n - k}
$$

模 $998244353$

函数给出 $0,1,\dotsc,m$ 处的点值

$1\le n\le 10^9,1\le m\le 2\times 10^4$

LOJ #6509. 「雅礼集训 2018 Day7」C

题意

给定一棵 $n$ 个点的树，树上每个点初始有一个 $0$ 或 $1$ 的数字。

考虑这样一个过程：

1. 等概率随机选择一个点作为起点
2. 等概率随机选择一个新点并沿着树上的路径移动过去，最后反转这个新点上的数字（注意只反转这个新点上的数字而非经过的所有点的数字）
3. 如果此时整棵树上的所有数字相同，则过程结束；否则回到步骤 $2$

求出期望的移动距离，对 $10^9 + 7$ 取模。

$n\le 10^5$

Luogu P4705 玩游戏

题意

有长度为 $n$ 的序列 $a$ 和长度为 $m$ 的序列 $b$

对于 $k=1,2,\dotsc,t$ 求随机两个元素 $a_i$ 和 $b_j$，$(a_i+b_j)^k$ 的期望

模 $998244353$

$n,m,t\le 10^5$

可能就存个板子，而且先咕了

来更了

参考 毛啸《再探快速傅里叶变换》

好久没写博客了，不过修了好多以前文章的锅。

描述

给出一张 $n$ 个点 $m$ 条带权边的有向图，钦定一个根 $r$，求以 $r$ 为根的最小有向生成树（Minimum Directed Spanning Tree，MDST，也即最小树形图）。

有向生成树（DST）即要求边是从父亲连向儿子。

下面给出的算法可以在 $O(n\times m)$ 的复杂度内求解，另外存在更优的算法。

本文定期不更新

故事

要 WC 了，不用 Linux 会爆零的

先装了 Ubuntu 18.04 LTS ，然后被下面这个 DNS 的问题搞得心力交瘁，好久之后就放弃了

卸了装 16.04 LTS ，没有这个问题

再升 18.04 ，还是有这个问题，但是解决了

问题

求以下形式表达式的值。

$$ \sum_{i=0}^n i^{k_1}\left\lfloor \frac{a\times i+b}{c} \right\rfloor ^{k_2} $$

写题解好慢啊

就记一下做的题吧

Codeforces 1034E

题意

给你两个 $2^n$ 的数组 $a_0,..,a_{2^n-1}$ 和 $b_0,..,b_{2^n-1}$

在模 $4$ 意义下求子集卷积

$n\le 21$