莫比乌斯反演习题:bzoj 1257 [CQOI2007]余数之和

题目描述

给出正整数$n$和$k$,计算$f(n, k)=k \text{ mod } 1 + k \text{ mod } 2 + k \text{ mod } 3 + \cdots + k \text{ mod } n$的值

阅读全文

莫比乌斯反演

阅读全文

01trie

简介

trie(retrieval)树,一种存储多个有序序列的树,在存储前缀相等次数多的数据时有很大的优势

一般来说,trie树是用于字典树,但这篇文章不谈字典树,而谈一谈它的近亲——binary trie

阅读全文

斜率优化

何为斜率优化

对于一类动态规划问题,方程式诸如

$$
f_i=\max\{c_i + k_i \cdot x_j + y_j | j \lt i\}
$$

阅读全文

随机化算法与模拟退火

前言

在OI中,某些题是要求找一种方案,最大化或最小化某个值,此时可以选择动态规划、网络流、数学公式、线性规划、剪枝搜索、数据结构维护、二分三分等等,但如果想不出正确的方法的话,可以尝试随机化乱搞来大致骗分

阅读全文

二进制分组

一个想法

如果需要让你维护一个数据结构

支持往里面添加一个数据,或者查询一个信息

且强制在线,应该怎么做呢?

如果支持快速插入和快速查询的话,直接做就好啦

阅读全文

ODT

起源

codeforces 896 C

阅读全文

非旋转平衡树

所以这是啥……

在维护各种数据的时候,常用的方法是平衡树套上一堆东西

普通的平衡树主要面临几个问题

  1. 代码超长不易调试

阅读全文

对拍

简介

在OI中,对拍是不可缺少的一部分 没有对拍的比赛不是完整的比赛

由于不能保证自己写的一定是对的,所以需要对拍来检验正确性

阅读全文

(广义)后缀自动机

动机

如何储存一个字符串的所有子串?

怎么做

后缀自动机!

阅读全文