zhangxixi的博客

简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132978606 首先看到不能走出边界，发现是个反射容斥 对于此题，我们可以采用循环卷积来实现反射容斥 也就是说，如果我们走出了边界，相当于就是走到了另一边 而实现这个过程我们可以把卷完后 i+pi+pi+p 的部分直接平移到 iii 就行 加速这个过程可以用多项式快速幂 1234567891011121314151617181920212223...

对于每种情况分别统计概率来计算期望+树上连通块统计：ARC165E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132971902 https://atcoder.jp/contests/arc165/tasks/arc165_e 考虑一个常见套路，我们对每个连通块统计其概率，设为 p(T)p(T)p(T) ，则答案为 ∑∣T∣>kp(T)\sum_{|T|>k} p(T) ∣T∣>k∑​p(T) 可以想成对于每个大小大于 kkk 的连...

数位dp+判定转状态：Loj #6274. 数字 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132950029 https://loj.ac/p/6274 和位运算有关，然后值域范围又非常大，位之间关联不大，显然考虑数位dp 然后有上下界限制，直接来个4维 然后每一位考虑，先满足or的性质，然后考虑and 发现有冲突只会是（1,0）和（0,1） 首先如果发生冲突，则要么无限制，要么上界为1，下界为0 所以某位0的以后不会受上界影响，某位为1以后不会受下界...

二分套网络流：ABC320G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132927159 首先肯定先枚举数字 然后考虑二分答案 每个字符串向它合法的位置连边 然后易发现每个点出度最多为 nnn ，不然没意义 所以最多 O(n2)O(n^2)O(n2) 条边 然后跑网络流，看能不能流完，也就是能不能匹配成功即可 123456789101112131415161718192021222324252627282930313233343536373839404...

atcoder库中的网络流用法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132643984 头文件： 12#include<atcoder/all>using namespace atcoder; 定义： 1mf_graph<int>G(N); //N为边数 连边： 1G.add_edge(u,v,w); //u->v容量为w 最大流： 1int maxflow = G.flow(S,T,1e9); //从S流向T，初始...

FWT小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132922605 核心思想：把 a,ba,ba,b 化成 fwt(a),fwt(b)fwt(a),fwt(b)fwt(a),fwt(b) ，相乘后再化为 aaa 化的过程用的是分治 所以和FFT其实一模一样 OR / AND 卷积 不需要什么技巧，暴力分治转移即可 每次分治下去，相当于位数减一 注意合并过程中我们是计算对应位的贡献 因为其它位的贡献我们在分治下去时已经计算了 后面区间其他数贡献到前面...

FWT笔记存档 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132922560

异或前后 1 的个数的奇偶性 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132915268 一个常见套路 考虑异或操作，其前后1的个数奇偶性不会发生改变 因为每位要么没1，要么保留1个1，要么同时消掉2个1 这个结论可以方便我们构造fwt的转移系数

可能的模拟网络流部分思路整理（CF1408H） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093428 https://www.luogu.com.cn/problem/CF1408H 先转换 模拟网络流，所以要么割最上面一层，要么割最下面一层。 对于最上一层，肯定是左边连续+右边连续。 考虑枚举左边连续，对应到某些颜色节点，又对应到某些右边节点。 对右边节点建棵线段树，由于左边的点已经确定，先假设下面的和右边的点全部割掉。 右边的点全部割掉，所以...

哈夫曼树/合并果子中具有的单调性：牛客65157/F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132912243 正常哈夫曼树实现是用优先队列的 但是我们发现新建的节点大小满足单调性 那么我们就可以直接拿个队列来维护 但是一开始的节点和新的节点会混在一起 那就拿两个队列维护呗