[指数型生成函数+分治NTT+广义容斥]LOJ6503(雅礼集训 2018 Day4)【Magic】题解
题目概述有 $n$ 种颜色的膜法卡，每种颜色有 $a_i$ 种，总共有 $m$ 张。现在要把所有卡片排成一排，如果相邻两个卡片颜色相同则产生一个膜法对，求膜法对个数为 $k$ 的排列个数...
[思维+LCT]TopCoder【TreeColoring】题解
题目概述有 $n$ 个点的带边权树和 $m$ 次操作，每次操作：1.将一个点变成黑色。2.求 $x$ 到所有黑色点的距离。解题报告好像可以大力点分树……我没有想过。考虑我们要求的是 $\sum ...
[复杂度分析]LOJ6043(雅礼集训 2017 Day7)【蛐蛐国的修墙方案】题解
题目概述给出一个 $n$ 的排列 $\{p_n\}$（满足 $i\not=p_i$ ），求一个括号序列满足：1.是合法的括号序列。2.对于所有左括号 $i$ ，向 $p_i$ 连双向边，最后得到...
[DP]LOJ6501(雅礼集训 2018 Day4)【Cube】题解
题目概述定义 $0$ 维基础图形为点，$1$ 维基础图形为边，$2$ 维基础图形是正方形，$3$ 维基础图形是正方体，以此类推。问 $n$ 维基础图形由多少个 $m$ 维基础图形组成。解题报告感...
[DFS树+线性基+复杂度分析]UOJ138(UER #3)【开学前的涂鸦】题解
题目概述原来有 $n$ 个点的一棵树，现在加进了 $K$ 条边。问多少种方案删边使得图依然连通。解题报告非正解警告……接下来要讲的是原题解中的算法七，不过这个解法能艹标程（度教rank1，翰...
[二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解
题目概述给出一个 $n\times m$ 的巧克力，每个位置有形状和美味值，求一个个数最小的连通块满足形状数 $\ge K$ ，且在个数最小的前提下，美味值的中位数也要最小。解题报告人类智慧题Q...
[FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下 $1$ 的个数。给出 $a_0,b...
[斯坦纳树+随机]HHHOJ200【稗田的梦中之梦】题解
解题报告题目里要我们找出的实际上是一个满足条件的连通块，又因为数据范围这么小，所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,j$ 这个点与 $s$ 这些颜色连...
[斯坦纳树]BZOJ2595(Wc2008)【游览计划】题解
题目概述在 $n\times m$ 的网格上有 $k$ 个景点，选取每个网格都有代价，求最小代价使得景点之间全部连通。解题报告感觉这个东西好mogical啊……定义 $f_{i,j,s}$ 表示...
[期望的线性性+概率DP]TopCoder【RockPaperScissors】题解
题目概述有 $n$ 个骰子，每个骰子投出剪刀、石头、布的概率已知。现在每次随机拿出剩余骰子中的一个进行投掷（并不知道这个骰子的概率分布），投完后扔掉。你要出 $n$ 次剪刀石头布，赢了得 $3$...
