概念 快速沃尔什变换是一种类似 FFT，用来加速逻辑位运算卷积的算法。具体地，它被设计为用来解决以下问题： $$C_k=\sum_{i\oplus j=k}a_i\times b_j$$ 其中，$\oplus$ 表示位运算 $\lor, \wedge, \veebar$。直接枚举 $i,j$ 的复杂度是 $\Theta(n^2)$，FWT 能加速这个过程到 $\Theta(n\log n)$。 原理 前面说到它类似 FFT，因为它们都是通过先做一个变换，相乘，然后逆变换得到结果的，而变换的过程都是折半、分治。 我们定义变换为 $tf$，有 $$tf(C)…
概述 我们可以使用傅里叶变换来快速计算卷积。然而快速傅立叶变换具有一些实现上的缺点，我们必须做复数而且是浮点数的运算，因此计算量会比较大，而且浮点数运算产生的误差会比较大。 这个问题可以用数论变换解决。在模意义下，一些整数可以发挥单位复根的作用，使我们更精确地计算只有整数参加的卷积运算结果。 原根 概念 在 $FFT$ 中，我们利用了单位复根的以下性质： 1. $\omega_n^k$ 互不相同； 2. $\omega_{2n}^{2k}=\omega_n^k$； 3. $\omega_n^{k+\frac{n}{2}}=-\omega_n^k$ 4. 当 $k \neq 0$ 时，$1+\omega_n^k+(\omega_…
> AND HE THAT SHALL HUMBLE HIMSELF SHALL BE EXALTED. 这句话出自《马太福音》第二十一章，第十二节。它的中文是， > 凡自高的，必降为卑；自卑的，必升为高。 它是我博客首页的导语，也是我卑微而平凡的人生的指引者。尽管《圣经》没有让我成为一名虔诚的基督徒，但它的思想深深影响着我。 > Blessed are the poor in spirit, for theirs is the kingdom of heaven. Blessed are those who mourn, for they will be comforted. Blessed are the…
Description [https://codeforces.com/contest/1099/problem/F] Mitya 和 Vasya 在玩一个有趣的游戏。他们有一颗 $n$ 个节点，以 $1$ 为根的树。除了根之外的每一个节点 $i$，$p_i$ 是它父亲的编号。 对于树的每一个节点 $i$，它包含 $x_i$ 个曲奇，Mitya 需要 $t_i$ 的时间吃掉一块曲奇；在根节点有一块芯片，Mitya 可以花上 $l_i$ 的时间将它移至当前节点的任意一个儿子 $i$ 处。 Mitya 和 Vasya 将轮流进行如下操作（Mitya 先开始）： * Mitya 将芯片向当前节点的儿子移动；…
Description [https://codeforces.com/contest/212/problem/A] Berland 和 Beerland 之间有发达的航班网络，它们都属于 Berland 国营公司 BerAvia。每条航线将 Berland 的一个城市和 Beerland 的一个城市连接起来。 最近，Berland 决定私有化 BerAvia，他们将航线卖给了 $k$ 家私人公司。这些公司希望航线的划分尽量均匀。 具体地，对每个城市 $i$，定义不均匀度 $$w_i=\max_j a_{i,j}-\min_j a_{i,j}$$ 其中，$a_{i,j}…
Description 给出 $n$ 个询问，每次询问有多少个数对 $(x,y)$ 满足 $a\leq x\leq b, c\leq y \leq d$，且 $gcd(x,y)=k$。 Idea 首先我们可以差分一下，求下面这个函数的值。 $$f(k)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$$ 我们设 $$F(k)=\sum\limits_{k|d}f(…
引言 今天在一个手机论坛上，我和一位网友在 “精子进入卵细胞是否代表它跑得最快” 这个问题上产生了一点分歧，而我们之间的争论已经有上升到过激言论的趋势。 而我是一个认死理的人。我希望用较为科学的求证来解决这个问题。 我先把 层主 的原话放在这里： > 最早接触卵细胞的米青子是无法直接和卵细胞结合成为受精卵的，而是需要很多米青子渐渐腐蚀掉卵细胞外层的一层细胞膜才能有米青子和卵细胞结合，所以说你并不是跑的最快的，只是最幸运的。 我们先不谈 “所以” 之后的部分，单单看这之前的事实，层主有什么点是说对的嘛？ 完全错误。 接下来我从精子到达输卵管壶腹部开始，理一理受精的主要过程。 精子与卵透明带的识别和结合 必要结构 透明带 大多数哺乳动物的卵子排卵时并没有完成减数分裂，处于第二次减数分裂的中期。 卵子周围有两层成分包围，其一是透明带（zona pellucida, ZP），它是生长期的卵母细胞和颗粒细胞分泌的 非细胞成分，由 ZP1、ZP2 和 ZP3 三种糖蛋白组成；其二是卵丘细胞层，它是由卵丘细胞（cumulus cell，一种体细胞）和细胞间富含透明质酸的非细胞成分组…
题目描述 简单的题目，既是礼物，也是毒药。 B 君设计了一道简单的题目，准备作为 gift 送给大家。 输入一个长度为 $ n $ 的数列 $ a_1, a_2 , \dots, a_n $ 问有多少个长度大于等于 $ 2 $ 的不上升的子序列 $ a_{b_1}, a_{b_2}, \ldots, a_{b_k} $ 满足 $$ \prod\limits_{i = 2} ^ k \binom{a_{b_{i – 1}}}{a_{b_i}} \bmod 2 = \binom{a_…