小c的岛屿 题解
简单题还能写挂，感觉没救了啊 /fd /fd /fd题解由于保证每个点至少有一个出边，所以操作次数等于走的边数+1。由于这个步数可能到达 $\infty$，对于这种问题算期望的一种方法是：对于所有还没有停止的情况，算它们的概率的和。所以考虑一个暴力的 dp：设 $f_{i,j,k}$ 表示当前走了 $i$ 步（注意这里的步是指尝试加入了几次边，而不是走过的边数，最后答案减一即可），已经加入了...
简单题还能写挂，感觉没救了啊 /fd /fd /fd题解由于保证每个点至少有一个出边，所以操作次数等于走的边数+1。由于这个步数可能到达 $\infty$，对于这种问题算期望的一种方法是：对于所有还没有停止的情况，算它们的概率的和。所以考虑一个暴力的 dp：设 $f_{i,j,k}$ 表示当前走了 $i$ 步（注意这里的步是指尝试加入了几次边，而不是走过的边数，最后答案减一即可），已经加入了...
题目链接做法 1可以将其看成一个 $(n+1) \times (m+1)$ 的表格，其中 $f(0,m) = 0,f(n,0) = n^K$。这个递推式的组合意义就是每次可以走向量 $(0,1)$ 和 $(1,0)$，且第一次强制走 $(0,1)$ ，走到 $(n,m)$ 的方案数，这个方案数就是 $f(n,0)$ 贡献到 $f(n,m)$ 的次数。所以可以得到答案是：后面就是个自然数幂求和...
题目链接首先我们先考虑一维，并且坐标全都非负，有一个点在 $0$ 的情况。可以将每次的操作抽象成乘上一个多项式 $(1+x^p)$，然后系数在 $\bmod 2$ 意义下运算，要求等于最终的多项式。（所以操作顺序其实是没关系的）那么我们每次只需要找到一个能除的多项式尽量除就好了。具体地，我们每次找到距离 $1$ 最近的位置 $p$，然后除掉 $(1+x^p)$ 即可。如果有负数怎么办？发现这...
题目链接注意到两个排列本质不同，当且仅当它们的析合树不同。所以我们就是要对所有有 $n$ 个叶子的析合树计数。考虑析合树的性质：首先析合树是区分儿子顺序的，所以我们会思考能否用生成函数去表示一棵树。设 $F(x)$ 表示析合树的生成函数，其中 $[x^m]F(x)$ 表示有 $m$ 个叶子的析合树的个数，我们先不考虑 $[x^0]F(x)$ 是啥，之后要用的时候再特殊定义。那么下一步我们要考...
题目链接题解对于维护「某些元素之间必须贴贴相邻」这样的问题，可以考虑使用一种叫做 PQTree 的结构来维护。PQTree 上的点有三种类型：叶子结点，表示一个元素P 类节点，表示这个节点的儿子的顺序是可以任意排布的Q 类节点，表示这个节点的儿子的顺序必须是当前给出的顺序或者逆序现在我们考虑如何加入一个限制。设这一次限制是要求 $S$ 内的元素贴贴，那么我们把 $S$ 内对应的叶子都标记成黑...