zhangxixi的博客

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

回文自动机PAM小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132136120 https://www.luogu.com.cn/problem/P5496 类似AC自动机，维护两个指针，nxt和fail nxt表示当前回文串开头末尾都接a转移到哪 fail表示当前串最长broder PAM关键点：一个回文串的broder一定也是回文串，而且所有回文子串（末尾相同）都可以用此方法构造 然后转移和AC自动机类似。 几个理解上的易错点： fail...

异或和大小比较类问题——抓住最高位：CF1863F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132629186 https://codeforces.com/contest/1863/problem/F 因为有等于，所以考虑异或和为0的合法区间，它可以随意切 现在考虑切开后左边大于右边，可以发现左右边最高位可以互相抵消，似乎不太可做？ 此时可以换个考虑，考虑大区间的异或和的最高位，这一位在左右两个区间 恰好 有一位为1，而为1的那个区间就是...

类欧几里得算法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132718582 求 ∑i=0n⌊ai+bc⌋\sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloori=0∑n​⌊cai+b​⌋ 推式子步骤： 分类讨论 a=0a=0a=0 是个最简式子 b≥cb\ge cb≥c 或 a≥ca\ge ca≥c 由 f(a mod c,b mod c,c,n)f(a\bmod c,b\bmod c,c,n)f(amo...

atcoder库中类欧（类欧几里得算法）floor_sum用法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132701473 https://atcoder.jp/contests/practice2/tasks/practice2_c 求 ∑i=0N−1floor((A×i+B)/m)\sum_{i = 0}^{N - 1} floor((A \times i + B) / m)∑i=0N−1​floor((A×i+B)/m) 直接使用即可： 1ans...

基环树和点度数相关的计数：CF1863G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132696642 https://codeforces.com/contest/1863/problem/G 首先建图，然后分析出交换在图上的变化，发现每条点最多只有一个入边标粗，求最终形态。 首先可以猜答案为 ∏v(inv+1)\prod_{v}(\mathrm{in}_v + 1)∏v​(inv​+1) ，但是环上会有不合法的和重复的。 发现以下情况会重复： 总...

分治NTT/在线卷积 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132670095 https://www.luogu.com.cn/problem/P4721 已知 ggg ，求 考虑分治，现在在 [l,r][l,r][l,r] ，先计算 [l,mid][l, mid][l,mid] ，然后计算 [l,mid][l, mid][l,mid] 对 [mid+1,r][mid+1,r][mid+1,r] 的贡献。 计算左对右的贡献，就把左边的 fff ...

环上计数+计数转概率：ABC318EX 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132650494 https://atcoder.jp/contests/abc318/tasks/abc318_h 先转为概率， fif_ifi​ 表示 iii 个点两人都AC的概率， gig_igi​ 表示恰好一个人AC的概率。 两个人都AC，只能为全部自环， fi=1i!f_i=\frac 1 {i!} fi​=i!1​ 现在求 gng_ngn​ 。然后有个定理， ...

线性求逆元 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132650059 先暴力求出 1n!\frac 1 {n!}n!1​ 往回推出 1i!\frac 1 {i!}i!1​ 1i=(i−1)!i!\Large \frac 1 i=\frac{(i-1)!}{i!}i1​=i!(i−1)!​

用树形dp+状压维护树上操作的计数问题：0902T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647373 发现操作数 k≤6k\le6k≤6 ，可以考虑对操作进行 状压 。 然后找找性质，发现要么删掉一棵子树，要么进去该子树。可以视为每种操作有两种情况。 然后分讨一下当前该如何转移。 树形dp的顺序： 合并子树 考虑当前往上的边的方向 然后发现只需要记住最早一次保留操作就行。 对于连通块大小的限制，就看一下当前操作之前有多少个子...