Min_25筛

Min_25 筛 引入 $O(n^{3/4}/\log n)$ 求一些积性函数的前缀和 质数贡献 我们先求 $$ G(m)=\sum_{i=2}^{m}[i \in prime]f(i) $$ 假设有一个函数 完全积性函数 $f'$ 在质数处与 $f$ 取值相同。我们可以改为求 $$...

范德蒙恒等式

范德蒙恒等式 $$ \sum_{i=0}^kC_n^iC_m^{k-i}=C_{n+m}^k $$ 证明: 组合意义 右边式子的组合意义为从 $n+m$ 个物品中取出总共 $k$ 个的方案数。左边式子和右边式子组合意义相同。 生成函数 $$...

Codeforces Round #656 (Div. 3)

A 题意 已知 $\max(a,b),\max(a,c),\max(c,b)$。求 $a,b,c$。 解法 其中至少会有两个相同的否则不存在。假定 $a$ 为最大值。则 $b=\min(\max(a,b),\max(a,c),\max(c,b))$ ,$c$为小于等于 $b$ 的一...

Codeforces Round #655 (Div. 2)

A 题意 输出 $n\le 1000$ 个小于 $1000$ 的正整数,使得不存在 $a_x+a_y=a_z$ 解法 $1,1,3,3,5,5….$ B 题意 给定 $2\le n\le 1e9$ ,输出 $a,b$ 使得 $a+b=n$ 且 $\text{LCM}(a,b)$ 最小 ...

FWT

引入 求 $$ \sum_{i=1}^n c_i=\sum_{j\oplus k=i} a_jb_k (n\le 1e5) $$ 其中 $\oplus$ 表示一种二元位运算 与、或 正变换 对于 按位或 运算,我们若有 $i\ \text{or}\ k=k$ 和 $j\ \text{or}\ k=k...

2020牛客暑期多校训练营(第一场)

H 题意 多组数据,每组数据给出一个费用流和多个查询,查询为在每条边的容量都为 $\frac{u}{v}$ 的时候,从原点输送 $1$ 个单位的流量到汇点所需的最小费用。 解法 注意到每条边的容量都相同,而 $\...

莫比乌斯反演

莫比乌斯函数 $$ \begin{equation} \mu(n)=\left\{ \begin{array}{lr} 1 \qquad\qquad\qquad n=1\\ (-1)^k\qquad\qquad n为k个不同素数的乘积 \\ 0\qquad\qquad\qquad 其它 \end{array} \right. \end{equatio...