题目链接：[Ynoi2008] stcm

题意：

给定一棵树，可以维护一个集合，支持以下操作：

1. 当前集合中插入一个节点 $x$。
2. 撤回上一次插入操作。
3. 将当前点集标为第 $i$ 个点的子树补信息。

一个点 $x$ 的子树补信息定义为：树的点集除去 $x$ 的子树（包括 $x$）内的点得到的集合。
要求在 $4.5\times {10}^6$ 次操作以内，标记所有点的子树补。
$1\le T\le 3,1\le n\le {10}^5$。

- 阅读剩余部分 -

题目链接：重返现世

题意：

有 $n$ 个元素，每次抽取到第 $i$ 个的概率是 ${\displaystyle \frac{p_i}{m}}$，求抽到任意不同 $k$ 个的期望次数。

$1\le n\le 1000,1\le m\le {10}^4,0\le n-k\le 10,\sum p_i=m$。

- 阅读剩余部分 -

前言

这东西看起来我早就会了，只是一直没有理解其原理。/kk

- 阅读剩余部分 -

题目链接：[MtOI2018]情侣？给我烧了！

题意：

有 $n$ 对情侣，电影院有 $n$ 排共 $2n$ 个座位，每排 $2$ 个座位，求恰好 $k$ 对情侣坐在同一排的方案数。

$1\le T\le 2\times {10}^5,1\le n\le 5\times {10}^6,0\le k\le n$。

情侣？给我烧了！

- 阅读剩余部分 -

前言

群除我会，来学一波。

本学习笔记基本参考【IOI2020 论文集】虞皓翔，浅谈群论在信息学竞赛中的简单应用

- 阅读剩余部分 -