牛客237787563号

未归档

/ 注册

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

省选模拟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

省选模拟41 题解

A. 要换换名字显然二分一个答案，然后问题转化为二分图中是否存在一组完美匹配。然后发现，如果一个字符串的子序列个数超过 $n$ ，那么就没有必要接着连边了。所以对每个字符串建出不超过 $n$ 条边，然后跑个网络流就完事了。 B. 动态半平面交因为太菜了，所以只会用一些套路来做...

数学二分图二分答案差分网络流线段树

2020-03-09

0 359

省选模拟44 题解

A. 跑步对于每次修改，$O(n^2)$ 的 dp 是显然的。然后发现每次修改这个 dp 的变化量只有 $+1,-1$ 两种取值。继续观察性质，可以发现，对于每一行，变化的位置是连续的。对于不同行，变化的左端点和右端点都是单调的。所以通过树状数组差分实现区间修改，单调指针确定每一...

dp 树状数组数学线段树

2020-03-13

0 368

省选模拟51 题解

A. 数学利用本题的特殊性质，可以得到如果 $n$ 为奇数，那么答案为 $(ab)^{\frac{n+1}{2}}$ ，对这个玩意平方一下即可发现是对的。对于 $n$ 为偶数，可以把 $2$ 全都提取出来，然后对剩余的部分取得一个解。然后不断缩小 $2$ 的次数以迭代，当缩小为 $2^0...

数学构造题 dp bitset 网络流

2020-03-22

0 410

省选模拟73 题解

A. 决战因为把暴力放过去了，所以这题就成水题了。其实正解的做法与那道求匹配方案权值和的题在链上的情况很类似。大概就是说整一个分治出来，然后 $dp_{l,r}$ 处存放一个多项式。其中 $l,r$ 分别表示左右两个端点的状态，$x^k$ 项系数表示放置了 $k$ 个人的方案数。 ...

莫比乌斯反演分数规划二分答案多项式数学网络流

2020-04-17

0 383

省选模拟75 题解

A. 比特币考虑把第 $k$ 位为 $1$ 的问题放在模 $2^{k+1}$ 意义下考虑，这样问题就简单了。因为若干个循环的贡献被强制放在了同一段上考虑。然后随便弄个数据结构维护一下即可。 B. 测试类似约数个数和一题，可以用类似的构造方法来展开 $d(i*j*k)$ 这个函...

数学莫比乌斯反演多项式 dp 斯特林数

2020-04-20

0 403

省选模拟85 题解

A. rng 有这样一个想法，我们把实数值域变成整数的。具体来说就是把给每个区间的 $r_i$ 都减去 $1$。这样的话期望就不难计算了：以值域作为下标，修改就是每次把 $[l_i,r_i]$ 区间加上一个 $\frac{1}{r_i-l_i+1}$。每次查询逆序对，其实就是求这个...

dp 莫比乌斯反演数学线段树

2020-05-01

0 409

二次剩余

二次剩余 PS:以下内容大概都是抄的。大概是解这样一个方程： \[x^2 \equiv n \pmod p \] 这里讨论 \(p\) 为奇素数。称非 \(0\) 数 \(n\) 是二次剩余当 \(n\) 存在上述方程的解，反之成为非二次剩余。二次剩余的数量为 \(\fr...

数学

2020-07-22

0 486