min-max容斥
min-max容斥
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133698526
设 都是可重序列
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-10-09
用min-max容斥实现lcm与gcd互换
用min-max容斥实现lcm与gcd互换 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133698576 lcm本质是每个质因子质数取max，gcd是每个质因子质数取min 然后我们就可以直接套min-max容斥：
2023-10-09
二维反射容斥：P9366
二维反射容斥：P9366 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133707260 https://www.luogu.com.cn/problem/P9366 构造循环矩阵，考虑反射容斥和将军饮马 考虑二维不太好做，我们曼哈顿距离转切比雪夫距离，变成一维的情况。 由于棋盘是正方形的，所以循环长度为 2n+42n+42n+4 。用多项式快速幂预处理，询问记得考虑正负两个方向。 123456789101112131415161718192021222...
2026-07-04
初等数论入门 Lesson 4 莫比乌斯反演
初等数论入门 Lesson 4 莫比乌斯反演 线性筛求 μ(1…n) μ(1)=1\mu(1)=1μ(1)=1 若 iii 是素数：μ(i)=−1\mu(i)=-1μ(i)=−1 若 imod pj=0i\mod p_j=0imodpj=0，即 pj2∣ip_j^2\mid ipj2∣i，则 μ(i⋅pj)=0\mu(i\cdot p_j)=0μ(i⋅pj)=0 否则：μ(i⋅pj)=−μ(i)\mu(i\cdot p_j)=-\mu(i)μ(i⋅pj)=−μ(i) 基础函数与Dirichlet卷积 单位函数（卷积单位元） ε(n)={1,n=10,n>1\va...
2023-10-10
期望+拆贡献+充斥：CF1349D
期望+拆贡献+充斥：CF1349D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753187 第一步：找性质 每个人的期望步数只与总数量 mmm ，总人数 nnn ，自己数量 aia_iai 有关 第二步：转化（难点） 拆贡献：拆成每个人win的期望步数，然后求 ∑E(i)\sum E(i)∑E(i) 容斥：肯定不能直接算。于是考虑算直到第 iii 个人拿完才结束的的期望步数 继续拆贡献：考虑具体容斥。就是算每个人对这个人拿完的贡献， ...
2026-07-26
博弈论找性质mex用容斥+NTT优化：26暑杭电 2-05
博弈论找性质mex用容斥+NTT优化：26暑杭电 2-05 1005 减数游戏 2 博弈 先把博弈论的问题解决掉，怎样是最优的。 目的是让对手尽可能地吃掉有的数 我们来看一个数轴： 只要蓝色是先手： 奇数连续段时，它必然比绿色少吃1个 偶数段时，它和绿色相等 而且通过上面这种策略，它每次都可以占据空白段。 因此，关键在于谁能获得空白段的主动权 而空白段的主动权，只和第一个连续段的长度有关。 如果第一个连续段长度为偶数，那么先手就必胜了。 容斥 不妨令 mex(S)=p\text{mex}(S)=pmex(S)=p，在 1∼p−11\sim p-11∼p−1 内有 rrr 个空，...
2023-10-09
质因子拆贡献+朴素容斥：1007T3
质因子拆贡献+朴素容斥：1007T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133697910 http://cplusoj.com/d/senior/p/SS231007C 考虑枚举gcd，然后容斥，恰好转至少。 ggg 表示gcd恰好为 ddd ， fff 表示至少为 ddd 显然有 f(d)=∑d∣ng(n)f(d)=\sum_{d|n}g(n)f(d)=∑d∣ng(n) ，可以直接莫反成： g(d)=∑d∣nf(n)μ(nd)g(d)=\s...