zhangxixi的博客

最小数（欧拉定理） 本文搬运自本人高中时期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关系式 + 欧拉函数） 本文搬运自本人高中时期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 奇数国（欧拉函数） 本文搬运自本人高中时期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 ...

杜教筛入门 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142208852 求 fff 的前缀和（不要求 fff 为积） 考虑 h=f∗gh=f*gh=f∗g ，若 h,gh,gh,g 前缀和都好求，那 fff 的前缀和 sss 是好求的 ∑i=1nhi=∑ij≤nfigj\sum_{i=1}^n h_i=\sum_{ij\le n}f_ig_j i=1∑n​hi​=ij≤n∑​fi​gj​ ∑i=1nhi=∑i≤ngi∑d=1⌊ni⌋fd\sum_{i=...

[SDOI2010] 地精部落（简单dp） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142138324 https://www.luogu.com.cn/problem/P2467 一开始想错方向，小丑了 设 f(i,j,0/1)f(i,j,0/1)f(i,j,0/1) 表示还剩 iii 个，上一个在剩余数里面排名为 jjj ，之前是上升/下降的方案数，转移显然 滚一下前缀和就好 123456789101112131415161718192021222...

[SCOI2014] 方伯伯的玉米田（dp+树状数组维护行列） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142137107 https://www.luogu.com.cn/problem/P3287 显然每次操作的区间一定是一个后缀 我们直接令 dp(x,i)dp(x,i)dp(x,i) 表示最后一个数是 xxx （加之后），加了 iii 次的最长长度，转移显然 max⁡dp(y≤x,j≤i)\max dp(y\le x, j\le i)maxdp(...

BZOJ3688. 折线统计（dp+ds） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142096597 https://hydro.ac/d/bzoj/p/3688 一个很显然的dp， f(x,k,0/1)f(x,k,0/1)f(x,k,0/1) 表示现在末尾的数为 xxx ，已经有 kkk 段线段，之前一直在上/下的方案数，转移显然。 然后前面一维我们遍历 iii 时只会修改一个 xxx ，同时查询其他前后缀的和，那直接树状数组即可。 1234567...