「BZOJ 4311」向量-线段树分治 + 凸包

维护一个向量集合,支持:

  1. 插入一个向量 $(x, y)$;
  2. 删除插入的第 $i$ 个向量;
  3. 查询当前集合与 $(x, y)$ 点积的最大值是多少,如果当前是空集输出 $0$。

查看更多

分享到

「LOJ 6053」简单的函数-ExtendedEratosthenesSieve

一个函数 $f(x)$,它满足:

  1. $f(1) = 1$。
  2. $f(p ^ c) = p \oplus c$($p$ 为质数,$\oplus$ 表示异或)。
  3. $f(ab) = f(a)f(b)$($a$ 与 $b$ 互质)。

求 $\sum\limits_{i = 1} ^ n f(i) \bmod 1000000007$。

查看更多

分享到

「SuperOJ 1297」数学题-ExtendedEratosthenesSieve

定义欧拉函数的变种
$$\phi(n, d) = \prod_{k = 1} ^ m (p_k ^ {e_k} + d)$$
特别的,$\phi(1, d) = 1$,求
$$\sum_{i = 1} ^ n \phi(i, d) \pmod {10 ^ 9 + 7}$$

查看更多

分享到

「BZOJ 4916」神犇和蒟蒻-ExtendedEratosthenesSieve

求 $A = \sum\limits_{i = 1} ^ n \mu(i ^ 2), B = \sum\limits_{i = 1} ^ n \varphi(i ^ 2)$

查看更多

分享到

「SPOJ DIVCNT[2/3/k]」-ExtendedEratosthenesSieve

求 $\sum\limits_{i = 1} ^ n \sigma_{0}(i ^ k)$,$n, k \leq 10 ^ {10}, T \leq 10000$。

查看更多

分享到

Extended Eratosthenes Sieve

扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ (这里以实际运行效果估计,实际复杂度据说和洲阁筛一样)求出一般积性函数的前缀和,消耗 $O(\sqrt{n})$ 的空间

查看更多

分享到

「模拟测试」背单词-AC 自动机+二进制分组

要求支持 $2$ 种操作:

  1. 向字典中加入一个串 $s$,其权值为 $v$(若重复算作多个串)。
  2. 询问一个串 $t$,其中在字典中出现过的单词的权值和(相同单词应被多次计算)。

强制在线。

查看更多

分享到

三模数 NTT 与拆系数 FFT

三模数 NTT 与拆系数 FFT

两个长度为 $10 ^ 5$ 级别的多项式相乘,对 $10 ^ 9$ 级别任意模数取模。

查看更多

分享到

「BZOJ 3510」首都-Link-Cut-Tree

维护一片森林,要求支持加边,询问重心,询问所有树重心编号的异或和。

查看更多

分享到

「BZOJ 5020」在美妙的数学王国中畅游-Link-Cut-Tree

维护一个森林,每个点有一个函数 $f$,要求支持连接两个点,断开两个点,修改某个点的函数,询问路径上函数 $f(x)$ 的和。

查看更多

分享到

「BZOJ 1396/2865」识别子串-后缀数组+单调队列

给定一个字符串 $S$,定义一个位置 $i$ 的识别子串为包含这个位置且在原串只出现一次的字符串,求每个位置的识别子串的长度。

查看更多

分享到

「BZOJ 5104」Fib数列-BSGS+二次剩余

求在 $\bmod 10 ^ 9 + 9$ 的意义下,数字 $C$ 在 $\text{Fib}$ 数列的哪个位置,无解输出 $-1$。

查看更多

分享到

「hihoCoder 1236」Scores-分块+bitset

给 $n$ 个人,每人有 $5$ 科成绩,给出 $q$ 个成绩查询,输出 $5$ 科都比要查询的这 $5$ 科低的数目。

查看更多

分享到

「CodeVs 2819」无尽的毁灭-Voronoi 图

给出 $n$ 个关键点,求出满足以下条件的点的个数及坐标:

  • 距离它最近的关键点有至少 $k$ 个

查看更多

分享到

「模拟测试」小店购物-块状链表

有 $n$ 种物品,个数无限,价值为 $w$,价格为 $p$,要求支持单点修改,询问 $k$ 元能买的最大价值,要求优先购买能买的物品中价值最大的,相同价值选择价格小的。

查看更多

分享到

「模拟测试」纸带-线段树/set/并查集

给出一个序列,每次操作将 $[l, r]$ 染上一种颜色 $i$,问最后有多少种颜色。

查看更多

分享到