组合数学

今天有点人品，T1的50pts暴力怒压正解。。这数据。。不言而喻 $\text{score: 100 + 0 + 0 = 100 rk: 7/36}$ Problem A：时间管理带师题目描述众所周知，罗老师是时间管理带师 因为罗老师是时间管理带师，所以他的时间是以东为单位的 具体来讲，罗老师一天有nn东的时间 现在有很多妹子想跟罗老师约会 奇特的，她们每天总会提出两段约会时间（可能相同，代表一种），并且每天提出的总是一样的。 她们提出的约会时间形式形如i,j,代表希望在[i东,(i+1)东)[i东,(i+1)东)或[j东,(j+1)东)[j东,(j+1)东)与罗老师进行约会。 当然，罗老师可以这两段时间都与这个妹子约会,只选择一段，或者伤心地抛弃。 那么，作为时间管理带师的罗老师，每天会选择尽可能多的妹子进行约会 但你一定要注意,罗老师最近并不打算进行多人运动，所以他不会在1东的时间同时与两个或多个妹子约会 罗老师并不脸盲，与一个妹子约会2次并不能算成”2”次的贡献，只能是”1” 罗老师是时间管理带师，只要满足以上条件，他就可以安排好他的时间，不用担心别的 而且,每天可能会有新的 ...

晚了几天写，暴力场 $\text{score：40 + 40 + 45 = 125 rk：17/30}$ Problem A：Tree题目描述 数据范围对 $100\%$ 的数据，$1 \le n \le 10^8, ~ 1000 \le k \le 10^8$ 题解很容易发现，满足条件等价于要求树中没有任意一条从根出发的路径经过超过 $k - 1$ 个左儿子 然后就是一个很妙的转换，将树按如下规则变为括号序列： 子树 $u$ 括号序 = ‘(‘ + ‘$u$ 左子树括号序’ + ‘)’ + ‘$u$ 右子树括号序 给个题解的图例 实际上可以不用考虑叶节点，那么现在将 $n$ 变为 $n - 1$，$k$ 变为 $k - 2$ 那么现在的任务就变为在坐标系中将左括号看作往右上角走，右括号看作往右下角走，从 $(0, 0)$ 最终走到 $(2n, 0)$ 的方案数，并需要满足过程中纵坐标始终在 $[0, k]$ 中的方案数（注意此时 $n, k$ 已变化） 这就是类似卡特兰数，但是有两条限制，即不能碰到 $y = - 1$ 也不能碰到 $y = k + 1$ 又从 $(x1, y1 ...

该文为（金策《生成函数的运算与组合计数问题》）学习笔记 幂级数级数：一个有穷或无穷序列 $a_0, a_1, a_2, …$ 的形式和「即 $\sum\limits_{i = 0} a_i$」被称为级数，序列中的项称作级数的通项 敛散性：极限是无穷即为发散「如 $f(x) = x$」；极限不为无穷即为收敛「如 $f(x) = \frac{1}{x}$」 那么幂级数即为形如 $\sum\limits_{n = 0}^{\infty} a_n(x - c)^n$ 或者化简为 $\sum\limits_{n = 0}^{\infty} a_nx^n$ 的形式 形式幂级数形式幂级数$$A(x) = \sum\limits_{n = 0}^{\infty} a_nx^n$$形式与幂级数很像，但这里 $x$ 作为一个符号而不用具体数值带进去算，也不研究敛散性什么的 形式幂级数的加减乘法与多项式的有着类似的定义 实际运算时一般在 $\bmod{x^n}$ 的意义下进行，即仅取次数不超过 $n - 1$ 的项 笛卡儿积「直积」有集合 $A, B$，则 $A, B$ 的笛卡儿积记作 $A \times ...

题意将题意转化一下 有 $m = \sum\limits_{i = 1}^n w_i$ 个数，前 $n$ 个中第 $i$ 个为 $w_i − 1$ ，剩下的 $m − n$ 个数都是 $− 1$ 求对这 $m$ 个数 $m!$ 种重排的方案中，有多少种满足重排后的序列任意前缀和不为负 题解卡特兰数的另一种组合意义首先有一个引理 给定 $n$ 个 $1$ 和 $n$ 个 $- 1$，它们组成一个长度为 $2n$ 的序列 $a$，则必定存在一个 $i$ 使得序列 $a_{i + 1…2n} + a_{1…i}$ 满足任意前缀都不小于零 证明也很简单，找到一个使得前缀和最小的位置 $i$，设 $s_{i,j}$ 表示 $a$ 上 $a_i$ 到 $a_j$ 的和，那么显然 $s_{i + 1, 2n} \ge 0$，对 $\forall k \in [1, i]$，$s_{i + 1, 2n} + s_{1, k} \ge 0$ 那么接下来求解 $n$ 个 $1$ 和 $n$ 个 $- 1$ 组成的合法序列（即任意前缀和不小于零）的方案数，也就是卡特兰数 $1$ 的编号为 $1 \sim ...

这题一直往 $\text{dp}$ 去想，然后就没了 所以其实并不用注意之前的可看见的建筑的最大值是多少，若把那些能够被看见的建筑之间构成的区间看作一个小组，那么能够被看见的建筑不过是在当前小组中选择一个最大值最为代表排在左（右）边罢了 所以现在问题转化为将 $n - 1$ 个建筑分在 $A + B - 2$ 个盒子，然后盒子内可以随意排列的个数 然后上述问题实际上可以将每个盒子看作一个圆，故问题又转化为 $n - 1$ 个建筑构成的 $A + B - 2$ 个圆排列方案数，即斯特林数 $S (n - 1, A + B - 2)$ 然后要在其中选择一些放左（右）边，故答案即为$$ans = S (n - 1, A + B - 2) \times \dbinom{A + B - 2}{A - 1}$$ 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include <iostream> ...