Blog

题目大意

给定 $N$ 个 $6$ 面色子，价值为 $C_i$，每一面的概率均为 $\dfrac 16$，且有不同的权值 $A_{i,j}$。

从中选 $K$ 个色子，使得期望权值和的平方减去所选色子价值和最大。

题目大意

对于 $n$ 的唯一分解 $n=\prod p^c$，定义 $f(n)=\max\{c\}$。

$T$ 组询问，给定 $n,m$，求
$$
\sum_{i=1}^n\sum_{i=1}^mf(\gcd(i,j))
$$
$T\le 10^4$，$n,m\le 10^7$

题目大意

给定 $n$ 个数 $a_i$，对于每一个 $i\in[0,K-1]$，求选出 $m$ 个数使得异或和为 $i$ 的方案数。

$m\le n\le 1.3\times 10^5, a_i<K\le 2^{17}$。

模板

题目大意

给定 $n$ 个可重集 $S_i$ 及 $x,y,z,k$，每个可重集仅包含三种元素 $a_i,b_i,c_i$，且它们的个数分别为 $x,y,z$。对于每个 $t\in[0,2^k-1]$ 求
$$
\sum_{p_1\in S_1}\sum_{p_2\in S_2}\cdots\sum_{p_n\in S_n} [p_1\oplus p_2\oplus\cdots\oplus p_n=t]
$$
其中 $\oplus$ 表示按位异或。

$n\le 10^5,a_i,b_i,c_i< 2^k,k\le 17$。

Winter Camp Min-Max

题目大意

给定 $n$ 个节点的二叉树，给定叶节点的权值，非叶节点的权值有 $p$ 的概率为子节点的最大值，否则为子节点的最小值。

求根节点取到任意值的概率。

$1\le n\le 3\times 10^5$。

A

题目大意

给定包含 $\texttt{RGBrgb}$ 各一次的字符串，判断 $\texttt{r,g,b}$ 是否分别在 $\texttt{R,G,B}$ 之前。

快速傅里叶变换

点值表示法

在做多项式乘法时, 类似于竖式乘法, 一个朴素的想法是将一个多项式的每一项与另一个多项式的每一项相乘, 得到新的多项式, 时间复杂度 $\Theta(n^2)$。

我们考虑对多项式看作向量, 对其做线性变换, 其和系数表达是一一对应的, 从而可以在其变换上考虑。因此, 我们引入了点值表示。

A

题目大意

给定字符串 $S$，一次操作为 $S\gets rev(S) + S$ 或 $S\gets S + rev(S)$，求 $k$ 次操作后可以得到的字符串种数。

题目大意

给定 $n$ 个点 $m$ 条边的带权（长度）无向图，图中有 $k$ 个点，其中第 $i$ 个点有一辆自行车，有 $p_i$ 的概率损坏，只有到达该点才知道自行车是否损坏。

已知 Bessie 的步行速度为 $t$，骑车速度为 $r$，现在她从 $1$ 号点出发，求出一种路径方案，使得期望时间最短。

$1\le n,m\le 10^5$，$k\le 18$。