2023.4.22：ACM也退役力，不再更新。

奎若小哥镇楼！ヾ(≧∇≦*)ゝ！！！

因为首页摆着很多置顶文章感觉很奇怪而且看不到新文章了QAQ。

于是就整理了一些 长期更新&大型合集 的 文章&列表 ，一起列在下面：

• 奇技淫巧们
• BZOJ刷题记录（BZOJ已经爆炸了，不再更新）
• Codeforces Contest & Virtual Participation合集
• ZJOI2019省选讲课：数据结构水题选讲(By AwD)部分题解

• 多项式操作合集

  • 多项式乘法（卷积）：FFT，NTT
  • 任意模数多项式乘法：MTT
  • 多项式运算：多项式求逆，多项式开根，多项式除法/取模，多项式ln，多项式exp，多项式多点求值
  • 分治+FFT：cdq分治FFT，分治FFT（感觉就是启发式合并+FFT）
  • 哈夫曼树+FFT：就是……每次找出长度小的多项式进行合并QAQ

• 网络流建图技巧

  • 切糕模型
  • 最小割模型
  • 上下界网络流
  • 当点之间会出现环，要考虑奇偶拆分等方法把点拆成两半避免出现环。
  • 当费用小于等于 $0$ 时停止刷费用流，可以求出最大费用可行流（最小费用可行流同理）。

• 一些思路&公式

  • 左右端点均有限制，可以考虑倍增从而找到满足限制的最两边的点。
  • 动态树问题（LCT）如果会出现大量边的信息改动可以考虑建虚点。
  • Min_25筛可以筛一些能通过枚举素数+枚举素数/合数算出贡献的函数，比如次大质因数。
  • 有一种区间询问不重叠（可以代替ST表区间询问）的数据结构，戳这里。
  • 像 $\sum_{i=1}^{n}iq^i,\sum_{i=1}^{n}i^2q^i$ 这样的式子可以错位相减（好像是废话，大佬们不要在意QAQ）。
  • 概率为 $p$ 的事件每秒进行一次，期望 $1\over p$ 秒发生，证明戳这里。
  • $x$ 取值（范围在 $[1,n]$ ）的期望可以转化成：$E(x)=\sum_{i=1}^{n}P(x\ge i)$ ，证明戳这里。

  • 等差数列的乘积可以通过除以公差转化为阶乘：

    $$ a(a+d)(a+2d)\cdots(a+nd)={a\over d}({a\over d}+1)({a\over d}+2)\cdots({a\over d}+n)\cdot d^{n+1} $$

  • 对于线段树标记无法合并的问题，可以考虑分块，把标记记在每块的第一个位置上，并考虑如何从第一个位置推出其他位置的贡献，比如这题。
  • 整点三角形中的整点个数（不含边界）：设 $S$ 为三角形面积，$a$ 为三角形三边上整点的个数（不含顶点），则三角形中整点个数为 $S-{a+1\over 2}$ 。

• 错误大集锦

  • 注意FFT自带循环卷积，所以要记得清除掉用不到的值防止长度过大变成循环卷积。
  • wqs二分最后减去的不是求出来的个数，而是题目给出的个数！
  • 费用流中带点权的点一定要拆点而不是瞎搞（惨痛教训）。
  • 二分验证的时候一定要考虑到一些边界问题（比如树上问题可能要考虑根节点的特殊性）。
  • 编译的时候一定要带上题目中给定的参数，否则可能玄学CE。
  • 注意主席树和可持久化Trie的深度要 $+1$ ，因为有根节点（或者直接空间乱开……）。

• 注意事项

  • 先打会做的题，不要因为会做或者很水就跳过，最后可能会因为细节过多等突发情况导致来不及写。
  • 不要根据时间猜算法，尽量想优秀的做法（比如离线做法）。

• 简单卡常技巧

  • 少模少乘，少调用多维数组（可以开临时变量）。
  • 多维数组连续访问会快很多。

• 一些常用配置

  • Windows下调整栈大小：-Wl,--stack=XXX，其中XXX为字节数。
  • Linux下gdb调试时print & display输出大小限制调整：在/etc/gdb中更改gdbinit，加上set max-value-size unlimited。
  • Windows下对拍的随机种子可以用windows.h库中的GetTickCount()，Linux下对拍的随机种子可以用time(0)*clock()。
  • Emacs配置(For ZigZagK)：戳这里。