0%

min25 筛能够求解积性函数的前缀和。其时间复杂度为 $O(\frac{n^{\frac{3}{4}}}{\log n})$,空间复杂度为 $O(\sqrt n)$。

阅读全文 »

错排问题

递推:

$D(n)=(n-1)[D(n-2)+D(n-1)]$

容斥:

容斥的式子可以由二项式反演简单的推出来:不考虑 $i \neq a_i$ 这个条件,那么方案数即为 $n!$。这些排列中包含了所有恰由 $k(k=0,1,2,\cdots,n)$ 个位置不变的排列,因此有

使用二项式反演即可得到

阅读全文 »

数论函数

数论函数: 定义域为正整数的函数。

积性函数: 对于任意两个互质的正整数 $a, b$,均满足 $f(ab)=f(a)\times f(b)$ 的函数 $f$

完全积性函数: 对于所有正整数 $a, b$,均满足 $f
(ab)=f(a)\times f(b)$ 的函数 $f$

对于一个积性函数 $f$,$f(n)=f(\prod p_i^{a_i})=\prod f(p_i^{a_i})$,若 $f$ 还满足完全积性,则 $f(n)=\prod f(p_i)^{a_i}$

阅读全文 »

题意

给你 $n(n <= 10^9)$ 个盒子,初始全为空。有 $m(m<=50000)$ 个操作:

  1. 将编号为 $L$ 到 $R$ 的盒子里的石头数量变为 $(X-L+1)\times A \bmod B$,$X$ 为盒子编号;
  2. 查询 $L$ 到 $R$ 的盒子的石头总数。
阅读全文 »

多重背包问题:有 $n$ 种物品,每种物品有一个重量 $v_i$,价值 $w_i$,数量 $a_i$,问一个重量为 $m$ 的背包最多能装多少价值的物品。

阅读全文 »

线性基的构造

线性基是怎么构造的?

大概就是考虑每个数 $a$,从高位到低位枚举,找到在线性基 $b$ 中没出现过的 $a$ 的最高位 $i$,将 $a$ 加入到线性基$b[i]$中,高于 $i$ 的 $a$ 的二进制位用线性基中的数给异或掉(因此此时 $i$ 就是 $a$ 的最高位了)。然后用类似高斯消元的方法,先用下面的行消自己,再用自己消上面的行,把线性基消成一个上三角矩阵。

阅读全文 »