牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共11篇）

关于斯特林数

第一类斯特林数定义 $S_1(n,m)$表示$n$个元素，形成$m$个环的方案数，记作$\begin{bmatrix}n\\m\end{bmatrix}$。其中每个元素是不同的，每个环是相同的。递推公式从实际含义上去考虑，第一类斯特林数递推公式为： $\begin{bmat...

容斥组合计数数学斯特林数二项式反演

2019-12-11

0 295

省选模拟2 题解

A. 铁轨建设暴力插头dp+网络流判断可行性，可以拿到85分。然而这个题看起来就很像无限之环，只要稍微改一下建图就好了。然而这个建图还蛮难想到的。 B. 圈地游戏因为不会做+看不懂题解+std太长，所以咕掉了。 C. 组合数学 70分部分分：考虑到状态数很少，直接暴...

dp 网络流二项式反演容斥组合计数

2019-12-24

0 302

省选模拟26 题解

A. 染色问题不然想到一个50分的dp，然而我的dp转移和正解不一样所以没法优化所以就死了。。要是用我的dp推正解大概只能考虑实际含义。考虑每次在已有的颜色序列中间插入一段，那么考虑转移的方案数，不难得到一条dp转移路径的贡献是每次颜色序列长度+1的乘积。所以枚举一共经过了多少次转移，转...

dp 倍增多项式二项式反演容斥线段树

2020-02-22

0 293

省选模拟33 题解

A. 盗梦空间考虑首先构建一棵虚树，然后跑一遍多源点最短路，求出每个虚树上的点到达最近的关键点的距离。分类讨论最终的答案 $u$ 的出现位置。 1.出现在虚树节点的一个满足子树不含虚树节点的儿子子树中。一个很好的性质是我们只关注最大值。所以考虑对每个节点维护一个 multiset ...

容斥莫比乌斯函数二项式反演倍增数学虚树树剖

2020-02-28

0 253

省选模拟39 题解

A. gift 考虑把需要 $swap$ 的关系表示在图上。于是形成若干个环。容易发现交换的次数就是点数减环数。所以原题转化为环的计数问题。考虑把已有的每个连通块的部分表示出来。容易发现对于一条链我们并不关注中间是谁，只关注链首和链尾的状态，于是可以转化为五种形态。如果已...

lct 二项式反演后缀自动机容斥组合计数

2020-03-06

0 318

省选模拟40 题解

A. 染色问题考虑对每条边 $(a,b)$ 附加两种边权 $(x,y)$ 。对于一种染色方案，当 $col_a=col_b$，边权为 $x$，否则边权为 $y$。取 $x=1,y=0$，一种染色方案的贡献是所有边权的乘积，那么答案就是对于每种染色方案的贡献的和。发现这个玩意可以合并。...

组合计数状压网络流二项式反演

2020-03-08

0 660

省选模拟42 题解

A. coin 容易发现每种假钞的期望贡献是独立的。对于每种假钞，做一个 $n^2$的 dp 求出来选择 $i$张假钞的贡献。然后对这个贡献做一个背包就完事了。考虑一个东西，就是对于每种假钞，只能选择一个数目加入背包的贡献中。所以可以考虑对于每种假钞一张张加入贡献。然后发现发现...

矩阵树定理二项式反演 dp 2sat

2020-03-10

0 266

组合计数题解乱写

3.组合计数上 1.ARC102E 把当前限制对应的每个二元组提出来。枚举有多少个二元组中的数字出现了，然后问题是每个组中二选一。出现的数字可以出现 $>0$ 次，不在任何一个二元组中的数字可以出现 $\geq 0$ 次。统一一下就可以直接插板法了。 2.小Z的礼物通过...

二项式反演轮廓线容斥组合计数

2020-03-17

0 664

省选模拟53 题解

A. 数（number）对于 $n$ 为偶数，容易发现确定一半就行了，答案为 $10^{\frac{n}{2}}$。对于 $n$ 为奇数，列式子可以发现形如 $\sum 2x_i = \sum 2y_i \ \ +y_{mid}$。一步很神的操作是，把 $y_i$ 转化为 $9-y_i$...

容斥二项式反演二分答案贪心线段树

2020-03-25

0 290

省选模拟69 题解

A. 最小生成树因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，所以最优的策略肯定是将这棵树弄成一个菊花图。然后考虑把所有的边权按顺序列出来。如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。那考虑一个特殊的情况，如果说...

二项式反演多项式动态dp dp 分治构造题结论题容斥贪心

2020-04-13

0 295