1007C步行（树上贡献统计）
1007C步行（树上贡献统计） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142742718 http://cplusoj.com/d/senior/p/SS241007C 首先可以发现每条边的贡献为 2min(wx,S−wx)2\min(w_x,S-w_x)2min(wx,S−wx) ， xxx 为下端的点 考虑现在断一条边，连一条边。我们先不考虑断边，只连边。那么这是一个基环树，不在环上的贡献使容易算的 对于这个环，我们要先找出它的 www 变...
1007D. 航行（高消之把可以递推的丢到外面处理）
1007D. 航行（高消之把可以递推的丢到外面处理） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142742037 http://cplusoj.com/d/senior/p/SS241007D 前面64分显然，搜个状态，然后转移就行，这不是重点。 考虑我们现在高消的状态数太大，而我们实际上需要的只有 (x,0)(x,0)(x,0) 的状态，那它们之间能不能提前把关系推出来呢？ 假如当前速度是0，我们想知道到下一次速度是0的系数。而在这个过程中，肯定是只...
1007B逆序对（二维数点问题 窗口星星）
1007B逆序对（二维数点问题 窗口星星） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142741239 http://cplusoj.com/d/senior/p/SS241007B 显然这题是一个二维数点问题，我们要求在确定 [l,r][l,r][l,r] 下 iii 个数的最大值： l<i<rl<i<rl<i<r ar<i<ala_r<i<a_lar<i<al ...
1006C简单题（计数式子的组合意义 + DP式子联立）
1006C简单题（计数式子的组合意义 + dp式子联立） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142740338 http://cplusoj.com/d/senior/p/SS241006C 对于这个式子，我们可以从它的组合意义入手。 假设我们有 n+1n+1n+1 个白球要染色，中间有一个绿球，绿球左边有 aaa 个红球，右边有 bbb 球。染完后绿球左边每个白球有 xxx 的贡献，右边每个白球有 yyy 的贡献。 但接下来怎么做呢？这列出来...
最小数（欧拉定理）
最小数（欧拉定理） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142633615 http://noip.ybtoj.com.cn/contest/802/problem/7 对 nnn 进行一些简单处理，现在相当于变成了一个 n′n'n′ 和 11111…11111111\dots 11111111…111 的关系。 考虑这个东西不好表示，我们可以用 10l−19\dfrac{10^l-1}9 910l−1 来表示，现在变成了： 9n′=...
最小数（欧拉定理）
最小数（欧拉定理） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142633615 http://noip.ybtoj.com.cn/contest/802/problem/7 对 nnn 进行一些简单处理，现在相当于变成了一个 n′n'n′ 和 11111…11111111\dots 11111111…111 的关系。 考虑这个东西不好表示，我们可以用 10l−19\dfrac{10^l-1}9 910l−1 来表示，现在变成了： 9n′=...
集合统计（拆mod关系式 + 欧拉函数）
集合统计（拆mod关系式 + 欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142521016 http://noip.ybtoj.com.cn/contest/802/problem/6 对于： n mod k+m mod k≥kn\bmod k+m\bmod k\ge knmodk+mmodk≥k ，我们可以先把 mod \bmodmod 拆掉： n−⌊nk⌋×k+m−⌊mk⌋×k≥kn-\lfloor \dfrac n k\rfloo...
欧拉函数 简单题
欧拉函数 简单题 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142256434 φ(n)\varphi(n)φ(n) 表示 nnn 以内和 nnn 互质的数的个数 若 nnn 为质数 φ(n)=n−1\varphi(n)=n-1φ(n)=n−1 φ(pk)=pk−pk−1=pk(p−1)\varphi(p^k)=p^k-p^{k-1}=p^k(p-1)φ(pk)=pk−pk−1=pk(p−1) φ(n)\varphi(n)φ(n) 为积性函数...
P4140 奇数国（欧拉函数）
P4140 奇数国（欧拉函数） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142456348 https://www.luogu.com.cn/problem/P4140 等价于我们要求一个区间的积的欧拉函数，单点修改，每个数的最大质因子不超过281. 求积是容易的，然后现在只要求每个因子是否出现。 因为不超过60个因子，所以我们直接暴力即可。 直接树状数组即可。 123456789101112131415161718192021222324252627...
区间线性基
区间线性基 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142330927 https://www.luogu.com.cn/problem/CF1100F 求一个区间的异或最大值。 固定右端点后，相当于求一个后缀的最大值。我们可以对现在的线性基进行一些处理。 线性基是肯定要记的，但是哪些线性基是有用的呢？我们对于线性基的每个主元加一个 posipos_iposi ，表示这个主元是哪个位置贡献的，那么只有 posi≥lpos_i\ge lposi≥l ...
