洛谷4451 [国家集训队]整数的lqp拆分
Luogu 分析 设 $g_n$ 为 $n$ 的答案，则 我们只需要求 $[x^n]G(x)$，即 $\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$，而 $2$ 在模 $10^9+7$ 意义下是有二次剩余的，所以直接计算即可。 代码 // ==================================== // author: M...
标签 生成函数 下的文章
- 首页
- 生成函数
CF438E The Child and Binary Tree
Codeforces Luogu 分析 设 $s_i$ 表示 $i$ 是否在集合中，$f_i$ 表示权值和为 $i$ 的二叉树数量，那么 多项式开根+多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =========...
洛谷4841 [集训队作业2013]城市规划
Luogu 分析 设 $f_i$ 为 $i$ 个点的无向连通图个数，$g_i$ 为 $i$ 个点的无向图个数，那么显然有 多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-bl...
51nod1850 抽卡大赛
51nod 分析 首先考虑一个暴力做法。 假设我们现在正在计算张三的期望收益。则根据期望的线性性，我们只需要求出张三抽到某一张卡时位于某一个排名的概率。 枚举张三抽到的卡（为了方便称这张卡为 A），然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个不是张三的人中有 $j$ 个抽到的卡比张三大的概率。设 $p$ 为第 $x$ 个不是张三的人抽到的卡比 A 大的概率，容易得到转移 这...
洛谷3706 [SDOI2017]硬币游戏
Luogu LOJ 分析 首先你需要看懂这篇题解。 设 $f_{i,j}$ 表示长度为 $i$ 时出现 $j$ 结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_{i,j}$ 的概率生成函数为 $F_i(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 设 $a_{i,j,k}$ 表示 $s_{i}[1..k]$ 是否等于 $s_j[m-k+1..m]$ 。 ...
洛谷5401 [CTS2019]珍珠
Luogu LOJ 分析 首先题目要求的其实就是方案数。 设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有 显然也是一个卷积的形式。 于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。 另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。 总结：这是一道好题，可是...
洛谷4548 [CTSC2006]歌唱王国
Luogu 分析 以下统一规定 $n$ 为字符集大小，$m$ 为名字长度。 设 $f_i$ 表示长度为 $i$ 时结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。 设 $f_i$ 的概率生成函数为 $F(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。 根据 YMD 的论文可以知道我们要求的就是 $F'(1)$ 。 分析一下可以列出这样一个式子 用 KMP / has...
洛谷4389 付公主的背包
Luogu 分析 考虑写出所有物品的生成函数 于是可以调和级数的处理出 $G(x)$，然后多项式 exp 即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #i...