牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共7篇）

模拟23 题解

A. mine 设dp(i,0/1/2/3,0/1)表示前i位，且第i位填入0/1/2/炸弹的方案数。当第i位填入1的时候，需要关注炸弹在1的左侧或者右侧，故加半维表示炸弹在1的哪一侧，当i为不为1，最后一维无意义。简单转移。 B. water 第一眼：直接考虑临...

dp 最小生成树莫比乌斯函数桶容斥

2019-08-16

0 407

模拟89 题解

A. 666 应当注意到一个结论：带着一个剪贴板进行删除操作是没有意义的。可以转化为粘贴之后删除。所以直接跑spfa求最短路。注意到答案不超过48，所以边权超过48的边可以忽略。 B. 1234567 显然用莫比乌斯函数容斥。发现答案为$\sum \lim...

线段树单调栈最短路数论分块莫比乌斯函数杜教筛

2019-10-27

0 430

数学专题测试2 题解

A. B $[n=1]=\sum \limits_{d|n} \mu(d)$ 于是考虑用莫比乌斯函数容斥出题意中的$[gcd=1]$。设$f_n$表示$gcd$为$n$的倍数的答案。 $g_n$表示$gcd$为$n$的答案。 $g_1=\sum \limits_{i=1}^n\mu(i)...

矩阵线性代数莫比乌斯函数多项式数列

2020-01-05

0 441

数学专题测试3 题解

A. young 大概的意思是说，由低到高考虑不同的二进制位。形成一个最小生成树，那么最高二进制位不同的情况一定只出现一次。所以除掉最高位之后的情况形成两个集合，递归下去$dp$就好了。一个技巧是，将每个方案的最小值的总和，即$\sum \limits_{i}min(i)$转化为$\s...

莫比乌斯函数组合计数多项式数学杜教筛

2020-01-12

0 414

省选模拟9 题解

A. Surprise me 直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。于是可以套用莫比乌斯反演。最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\su...

二分图虚树图论结论题莫比乌斯函数点分治提交答案

2020-01-17

0 654

省选模拟16 题解

A. GCD和LCM 简单莫比乌斯反演。因为有一个$a$的限制，我们离线询问，将询问按$a$排序。随时更新要维护来统计答案的数组就可以了。 B. 平面图给出了平面图，所以自然想到对偶图。如果知道平面图上每个点所连的边的顺序，一个平面图转对偶图的方式是：考虑给每条边开两个...

启发式合并并查集莫比乌斯函数

2020-02-02

0 360

省选模拟33 题解

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

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

2020-02-28

0 346