生成函数

再次垫底$\text{.jpg}$ $\text{score：20 + 0 + 10 = 30 rk：27/29}$ Problem A：sign题面 题解这题贼水，但我没想出来。。 我大概以为这不是数学所以没想到代入，或者是我忘记该点值表示可以 $O (\log A)$ 反正全村就我没到及格线 题解懒得写了，就搬出题人给的吧 事实上，这个做法不能通过。 考虑上面做法复杂度瓶颈是快速幂。一个简单的$\text{trick}$是对于一个固定的 $son_u = k$，令 $M = \lceil \sqrt{A} \rceil$，预处理出 $k^0, k^1, k^2, …, k^{M - 1}$ 以及 $(k^M)^0, (k^M)^1, …, (k^M)^{M - 1}$。这样单次求某个点值就可以用 $O (1)$ 次算术运算求得。 时间复杂度为 $O ((n + \sqrt{A})\sqrt{n})$。 以上是出题人提供题解 代码123456789101112131415161718192021222324252627282930313233343536373839404142 ...

好了，又是爆零的一天，恭喜我自己 $\text{score：0 + 0 + 0 = 0 rk：27/27}$ Problem A：小卖部题目描述ysgh 是一名数数大师。 现在小卖部有 $n$ 种商品，第 $i$ 种有 $a_i$ 个，价格为 $b_i$。 ysgh 总共去了 $Q$ 天小卖部，第 $i$ 天他只会购买编号在 $l_i \sim r_i$ 的商品。他的卡里有 $c_i$ 元，因此他只能购买价值和不超过 $c_i$ 元的物品。 ysgh 想要知道有多少种购买物品的方案。由于答案很大，你只需要输出答案对 $1000000007$ 取模后的结果。两种方案被认为是不同的当且仅当存在一种物品，其购买数量不同。 当然，ysgh玩了个小花招，你需要通过上一个询问的答案来推导下一个询问的参数。 数据范围对于所有测试数据，满足 $1 \le n \le 10000, ~ 1 \le Q \le 50000, ~ 1 \le a_i, b_i, c_i \le 1000, 1 \le l’_i, r’_i \le n$ 题解令 $C = 1000$ 首先看得出来可以用生成函数搞，显然答 ...

该文为（金策《生成函数的运算与组合计数问题》）学习笔记 幂级数级数：一个有穷或无穷序列 $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 ...

显然答案是总哈密顿回路数除以值得记录的竞赛图数 那么先求解总哈密顿回路数，考虑每个哈密顿回路会在几个值得记录的竞赛图中，则有$$Hamitons = (n - 1)!2^{C_n^2 - n}$$即总共有 $(n - 1)!$ 种哈密顿回路，然后剩下的边随便选 于是现在考虑值得记录的竞赛图数 首先如果一个竞赛图要有哈密顿回路，那么它至少要有一个包含所有节点的环，即该图是强连通的，并且显然非强连通竞赛图它一定不存在哈密顿回路，所以有结论 有且仅有强连通竞赛图存在哈密顿回路 那么问题转化为求解强连通竞赛图 发现正面难以求解，就考虑反面求解 设 $f_n$ 表示 $n$ 个节点的强连通竞赛图数，$g_n$ 表示 $n$ 个节点的竞赛图数（即 $2^{C_n^2}$），可得 $DP$ 方程$$f_n = g_n - \sum\limits_{j = 1}^{n - 1} f_jg_{n - j}\dbinom{n}{j}$$其中求解非强连通竞赛图部分是每次将拓扑序最小的强连通分量提取出来计数，那么剩下的点随意连接（注意，此时取的是拓扑序最小的强联通分量，故该强联通分量与其它连通分量的连边方 ...

首先普通 $DP$ 式子很好列 令 $f[i][j]$ 表示 $i$ 个小朋友分 $j$ 个糖果且每人至少一颗的答案，则有$$f[i][j] = \sum\limits_{k = 1}^j f[i - 1][j - k](Ok^2 + Sk + U)$$接下来用生成函数优化该式 令 $g[k] = Ok^2 + Sk + U$，则$$f_i(x) = f_{i - 1}(x)g(x)$$其中 $f_0(x) = 1$ 所以答案即为$$[x^M] \sum\limits_{i = 0}^A f_i(x) = [x^M] \sum\limits_{i = 0}^A (g(x))^i = [x^M] \frac{1 - (g(x))^{A + 1}}{1 - g(x)}$$ 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384 ...

对于 $n$ 个点组成的环大小为 $m$ 的基环树个数的问题，目前已知三种解法 解法一「动态规划」在环上每个点下面搭树的方案数，相当于是在完全图中制造生成树，然后提一个点（即环上那个点）为根，故可用 $n^{n - 2}$ 来计算 然后就可以很容易想到一种背包解法，把环随便找个地方断一下，把它看成序列，即可令 $f_{i, j}$ 表示环序列前 $i$ 个点，已经使用了 $j$ 个点做环下的树的方案数，显然$$f_{i, j} = \sum\limits_{k = 0}^j f_{i - 1, j - k} \times \dbinom{n - m - (j - k)}{k} \cdot (k + 1)^{k - 1}$$然后答案要对环进行圆排列，即 $ans = f_{m, n - m} \times \frac{A_n^m}{2m}$ 复杂度 $O (n^3)$ 当然这样复杂度比较高，可以考虑将已经拼好的连通块和已经拼好的一棵树连接起来，令 $f_n$ 表示 $n$ 个点的答案 当然，为了保证不会算重，需要有一个特征点，即保证点 $1$ 不会在环上，即$$f_n = \frac{n ...