冷滟泽的个人博客

2020-07-23 lengyanze 阅读(89) 评论(0)

本文中，所有的图都是指有标号图。 前置知识 一些简单的只限制点数的图计数问题 二元多项式基本运算 下面将这些问题分为无向图和有向图两类来分别讨论。 无向图计数 定义级数序列 (a_n(w))_{k=0}^{\in...

2020-07-07 lengyanze 阅读(57) 评论(0)

P4002 [清华集训2017]生成树计数 Tag：Prufer 序列 / 组合计数 / 多项式 我们使用 Prufer 序列来表示一棵树，在原图中的同一连通块中的点标为一种颜色。设第 i 个连通块的大小为 a_i，...

2020-06-12 lengyanze 阅读(106) 评论(0)

比较综合的一道图计数题目。 本文中，以大写字母表示对应小写字母数列的普通生成函数（OGF）。 前置知识 多项式全家桶（乘法，求逆，ln，exp） 欧拉变换 \operatorname{Euler}[F(x)]=\p...

2020-06-03 lengyanze 阅读(49) 评论(0)

首先转化题意，对于确定的两棵树，设它们的边集分别为 E_1,E_2，则 E_1\cap E_2 形成了一棵森林，当前方案对答案的贡献为 y 的连通块数次方，即 y^{n-|E_1\cap E_2|}。下面对本题的三问...

2020-05-26 lengyanze 阅读(50) 评论(0)

设 a_i 表示原数组，b_i 表示所有长度为 i 的区间的权值和。首先我们对于一对 (i,j) 求出 a_i 对 b_j 的贡献（点对点）。发现这实际上就是求有多少个长度为 j 的区间覆盖了位置 i，讨论左端点的范...