有临项交换和排序可以考虑逆序对。每次交换相邻逆序可以恰好减少一个逆序对，因而恰好逆序对个数次就可以排序完毕。 操作二的实质是将逆序对个数从 变成 ，因为每个逆序对反转后变成正序了，反之亦然。 因而每个操作仅使用前两个操作的最小代价是好求的。下文称作暴力还原的代价。 接下来引入操作 。首先注意到目前最优操作之和当前排列有关，和历史状态无关。更具体的说，是和当前逆序对有关。 考虑最后的策略是什么：

套路题。感觉没见过类似的套路最好都方法就是打张表。 一般这种博弈论通常不先考虑 SG 函数（而且这题似乎不是公平组合游戏）。通常考虑分析性质或者手完小样例。 不妨考虑 的必胜策略。注意到 Alice 无论下什么位置 Bob 都可以对称的下。 需要注意奇数的情况。Alice 可以下在中间。此时 Bob 只要不开始下中间旁边的两个点即可，每次 Alice 对着下的时候中间旁边的两个点至少有一个点可以

被黑题吓死了。 如何计算答案 首先需要注意酒桶和熊都是区分的，不要读错题目意思了。 不妨先来考虑一些简单的情况。 考虑 的情况。对于这种情况，实际上我们只能接受醉倒 头熊，因为要保证至少一头熊清醒。由于醉倒的熊的个数和用掉的床位是相等的，直接将 对 取 即可。 对于只有一个床位的情况：挨个试过去即可。 天最多可以区分 桶。 对于只有一天，但是允许醉倒很多熊：直接二进制分组。 然而其

怎么拖到现在才开始写题解啊。 我不会啊。这咋做啊。 首先就是整除并不好做。我们因此考虑使用 转化一下： 考虑左侧的 这个东西很像二项式定理，因此我们朝着这个方向去凑。考虑把 写成 的形式。 组合意义合并一下两个组合数： 提出一个 。 做变量代换 ，此时要把 替换成 。 显然 是 。将求和下标从 开始，然后就是标准的二项式定理！ 太棒了。但是考虑右侧的 怎么处理。 并不好

原题链接 INFO 题意简述 有 棵树在一条直线上，每颗树高都为 。每棵树倒下后会带倒同方向距离小于 的树。每次随机从左右两颗树中选择一个，被砍倒的树有 的概率向左倒下， 的概率向右倒下。求最后树覆盖的期望。 不难发现任意时刻剩下来的树都是一个区间。这时候就可以从区间 dp 的角度去考虑。 我们不妨设 表示当前剩下区间 的树，在 区间内

我们给每一杯可乐先乘上 让其变成整数。 我们希望构造 ，并且要最小化 。 特判 的情况。考虑把 乘到右边去，得到 移项得到 我们另 表示这个 。我们希望用最小的 让 到达 。我们每选择一个物品，就会让 增加 。 我们对于每个 建出点来，对于每个 ，从 向 连边。我们实际上要找出原图的一个最小环。对于每个 可达的点作为源点跑多源 BFS 即可。 对于任意一组可行解，我们可以

紧急学习矩阵树定理。 矩阵树定理 矩阵树定理讲的是以下内容： 对于图 定义度数矩阵为 邻接矩阵为 定义拉普拉斯矩阵 。 求出将拉普拉斯矩阵去掉一行一列的矩阵 的行列式就是原图的生成树个数。 酷炫算术魔法！ 但是为什么？ 实际上就是一个容斥原理。 不妨考虑行列式的展开式： 来看看这个式子到底有什么组合意义。 拉普拉斯矩阵的样子就是，对角线上是点的度数，剩下的点中两点之间有边时为 ，否则

出题人以为自己出了神仙 dp 题然后被矩阵树定理杀穿了。提交记录全是矩阵树定理做法。无敌了。 为了体谅出题人，本篇题解来说说 dp 做法（绝对不是因为我不会矩阵树定理！）。 感觉是被低估的题目啊。 下文所说的 均指原题的 ，也就是每次加入点后，新加入的点和原先的连边的点形成的团的大小。 首先需要考虑树的性质。树的性质是有 条边的联通的无环的图。 你发现肯定是要对某种满足条件的加边序列进行计数，

我不会啊。 首先观察一下题目描述。 “采购方式包含了她经过的结点的次序，以及她在每条路上买不买材料，但不计她在哪个商店买了什么”。 发现等价于满足“进去买东西的点的并集恰好等于全集”的方案个数。 显然直接求需要一个状压，并不是很优秀。 但是我们发现，“进去买东西的点的并集等于某个集合的子集”的答案是好求的，你只需要只在是子集的边上买东西即可，其它边只通过。 不妨另 表示走了 步，目前在点

题目相当于要求放置磁铁的方案数，使得相邻两个磁铁的间隔不小于 。 我会状压！用 记录每个磁铁是否放过，从左往右计算。然而这个题目 ，状压并不足以通过。 我们发现状压的问题在于我们知道放了哪些磁铁防止重复放置。我们可以考虑将磁铁按照一定顺序放置，但是这样就不能从左到右转移了，因为磁铁可能是乱序的。 不妨将磁铁按照从大到小排序，这样我们只需要在放下磁铁的时候考虑限制即可。此时在位置 放下一个 的