牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共29篇）

关于斯特林数

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

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

2019-12-11

0 428

省选模拟2 题解

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

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

2019-12-24

0 408

省选模拟3 题解

A. 好题很神仙的做法。考虑颜色数较小的情况，可以直接通过状压$dp$实现。对于颜色数较大，不妨通过随机数将每种颜色都映射到$k$的范围内。显然这个玩意不会使答案更优，但是这样不一定能找出正确的答案。然而算一下就可以发现，这个玩意的正确性高达$\frac{k!}{k^k}$，所以...

容斥 AC自动机

2019-12-24

0 325

数学专题测试1 题解

A. 解方程考虑没有任何限制的东西， m个元素分为n个连续的区间，直接用组合数插板法就好了。考虑如何去掉元素大于$a_i$的限制，只要给最终的元素个数减掉$a_i$就好了。考虑如何搞元素个数小于$a_i$的限制，不妨使用子集反演，要求的是恰好$0$个元素大于$a_i$。只要...

容斥 lucas定理组合计数数学多项式倍增 fwt dp 区间dp

2020-01-02

0 493

省选模拟15 题解

A. 倒计时考虑50%的部分分。分块来削这个数。后四位形成一块，预处理出9991~9999在前五位的最大值为0~9情况下分别会削到的值和削的次数。对于零散的后四位暴力削，这样就可以通过根号预处理，根号削$n$了。容易发现，对于$n$比较大，我们多分几次块，每次用较小一级的块来预处...

网络流后缀自动机分块容斥

2020-02-02

0 366

省选模拟26 题解

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

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

2020-02-22

0 388

省选模拟27 题解

A. 飞行棋由于题目中给出了一些奇怪的条件，所以大概可以想到暴力模拟这个过程迭代若干轮。考虑如何比较好的进行迭代的过程，处理出一个数组 $f_{i,j}$ 表示在恰好第 $i$ 轮从 $j$ 这个位置走到 $n$ 的概率。那么考虑随时维护一个数表示游戏还没结束的概率，每次加入一个数转移即...

dp 分治决策单调性容斥

2020-02-22

0 394

省选模拟32 题解

A. 送你一道签到题这个函数显然是个积性函数。刚开始的想法是可以直接考虑分开每个质因子，然后乘一块的贡献显然是正确的。后来一想这个玩意实际上就是 $id^k$ 点积上 $d(x)$ 的 $m$ 次卷积，所以肯定是积性的。然后看这个数据范围，显然要搞个 min25筛。然后一想，这...

容斥 trie树 min25筛 dp 数学

2020-02-26

0 295

省选模拟33 题解

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

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

2020-02-28

0 346

省选模拟39 题解

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

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

2020-03-06

0 410