数学全家桶

abv3Rpkg · 2025-01-04 17:05:26 · 个人记录

杜教筛

求积性前缀和，即 S(n)=\sum_{i=1}^nf(i).

某些不是积性的函数也可以，只要能找到一个合适的 g。

对于任意两个数论函数 f,g，有\sum_{i=1}^n(f*g)(i)=\sum_{i=1}^ng(i)S(\lfloor\frac{n}{i}\rfloor).

如果可以找到一个 g(n) 可以快速地求出 f*g 的前缀和及 g 的前缀和，则 g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)。

后半部分可以递归地上数论分块，求得的若干 S(n) 需要记忆化来保证复杂度。

总复杂度 O(n^{3/4})，若预处理前 O(n^{2/3})项，则复杂度降至 O(n^{2/3})。

多项式乘法

FFT

大家伙。

计算两个次数为 n 的多项式 F(x),G(x) 的乘积。

系数表示法计算乘积是 O(n^2) 的，而点值表示法仅需要 O(n)。尝试把两个多项式转化为点值表示，相乘再转化回去。

由拉格朗日插值法，n 次多项式需要 n+1 个点来唯一确定。在低于 O(n^2) 的复杂度下对于 n+1 个点计算任意一个多项式 F(x) 看起来也很扯，只能寄希望于这些点满足一些奇妙性质。

以下认为 n+1=2^k，如果不是就用 0 补齐高次项。

考虑将 n 次单位根 1,\omega_n,\omega_n^2,\cdots,\omega_n^{n-1} 代入 F(x) 求值。
将 F(x) 的系数奇偶分类，奇数分给 A，偶数分给 B。则 F(x)=A(x^2)+xB(x^2)。注意到：

因为 \omega_{n}^{k+n/2}=-\omega_{n}^{k}，所以

所以如果分别获得了 A(\omega_{n/2}^k),B(\omega_{n/2}^k) 的值，我们就可以一起算出 F(\omega_n^k) 和 F(\omega_{n}^{k+n/2})。而计算 A(\omega_{n/2}^k),B(\omega_{n/2}^k) 是一个规模更小的子问题，递归求解是可以的。

这是 O(n\log n) 的。将系数表示法转化为点值表示法仅需要将所有单位根取共轭（虚部取反），进行相同的操作并将结果的每一项 \times \frac{1}{n}。鬼知道为什么。

浅证一下吧。设 \{a_i\} 为 F 各项系数，b_i=F(\omega_n^i)=\sum_{k=0}^{n-1}a_k(\omega_n^i)^k，c_i=\frac{1}{n}\sum_{k=0}^{n-1}b_k(\omega_n^{-i})^k。那我们要证 c_i=a_i。直接展开。

关于单位根求和，既可以直接套等比求和，也可以在单位圆上看一眼。都行，无所谓。

具体实现上，会先找到 F(i) 经过一串区间内奇偶分类的操作后会落在哪里。将初始位置二进制反转后就可以得到最终位置。鬼知道为什么。

源码大概长这个样子。

int rev[N];
void shuffle(cmplx a[],int len){
    for(int i=1;i<len;i++){
        rev[i]=rev[i>>1]>>1|(i&1?(len>>1):0);
    }
    for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
}
void fast_fast_TLE(cmplx a[],int len,int flag){
    shuffle(a,len);
    for(int k=2;k<=len;k<<=1){
        int wid=k>>1;
        cmplx w1={cos(2*pi/k),flag*sin(2*pi/k)};
        for(int i=0;i<len;i+=k){
            cmplx w={1,0};
            for(int j=i;j<i+wid;j++){
                cmplx p=a[j],q=a[j+wid]*w;
                a[j]=p+q; a[j+wid]=p-q;
                w*=w1;
            }
        }
    }
    if(flag==-1) for(int i=0;i<len;i++) a[i].real/=len;
}

NTT

考虑我们用到了上述单位根的什么性质。

1. \omega_{2n}^{2k}=\omega_{n}^k
2. \omega_{2n}^{k+n}=-\omega_{2n}^k
3. (\omega_{n}^k)^2=\omega_{n}^{2k}

我们发现如果设 \omega_{n}^k=g^{(P-1)\frac{k}{n}}，在 \bmod P 下好像也满足上述性质。

（一个数 p 的原根 g 满足 g^{k} 是纯循环（由欧拉定理，\gcd(g,p)=1）且循环节为 \varphi(k)。p 是质数时即代表 g^0,g^1,\cdots,g^{P-2} 遍历 [1,P)。）

所以我们将上面的 \omega 全文替换便得到了单位根。

注意并不是所有模数都可以 \operatorname{NTT}。求单位根的时候我们将 (P-1) 除以了 n，我们需要让其是整数。模数是 998244353=119\times 2^{23}+1，允许我们递归 23 层 \operatorname{NTT}，即多项式最高不能超过 2^{23} 次。实际使用时不用担心，因为次数高了最先爆炸的是时限而不是正确性。

写出来大概长这个样子：

void faster_faster_TLE(int a[],int len,int flag){
    shuffle(a,len);
    for(int k=2;k<=len;k<<=1){
        int wid=k>>1;
        int w1=Pow(G,(flag*(P-1)/k+(P-1))%(P-1));
        for(int i=0;i<len;i+=k){
            int w=1;
            for(int j=i;j<i+wid;j++){
                int p=a[j],q=a[j+wid]*w%P;
                a[j]=(p+q)%P; a[j+wid]=(p-q+P)%P;
                w*=w1; w%=P;
            }
        }
    }
    if(flag==-1){
        int Ilen=Inv(len);
        for(int i=0;i<len;i++) a[i]*=Ilen,a[i]%=P;
    }
}

停时

贴一篇讲解，虽然现在看不懂一点

贴一篇能看懂一些的讲解

记一个随机现象中所有可能发生的结果（称为样本点）组成的集合为 \Omega，记 \omega 是一个随机试验的结果：\omega 是确定取一个 \in\Omega 中的元素，但是在正式试验之前我们不知道它具体取什么。

记 X(\omega) 为一个随机变量。X 本质上是一个函数，将样本点映射到数值上。这样来说 \omega 就很像一个生成种子。

记一个随机过程为一系列的随机变量的集合（序列？），每个元素对应着一个时刻 t。比如说像这样：\{X_0(\omega),X_1(\omega),X_2(\omega),\cdots\}。注意所有 X 的取值均依赖于一个 \omega，即一旦 \omega 确定了整个随机过程也定下来了。把 \omega 略掉不写是可以的。

定义鞅为“未来的值的期望等于当前的值”的随机过程。形式化来讲，若随机过程 \{X_t\}_{t\geq 0} 对于每一个时刻 t 满足 \mathbb{E}(X_{t+1}|\mathcal{F}_t)=X_t。其中 \mathcal F_t 表示截至 t 时刻所获得的随机过程的信息(?)，即 X_0,X_1,\cdots,X_t。（应该是，只确定了这些 X 的值，而 \omega 仍然不确定？这句话是自己瞎猜的。）

一个鞅的停时 \tau 是一个随机变量，满足 \forall t\geq 0,\{\tau=t\}\in\mathcal F_t，即到任意时刻时我都知道当前该不该停下来。

停时定理

叙述如下：

设 \{X_t\}_{t\geq 0} 是一个鞅，\tau 是停时，如果满足以下条件之一：

• 【censored】
• 【censored】
• 【censored】

则 \mathbb{E}[X_\tau]=\mathbb E[X_0]。
（条件是什么不重要，即使知道也不一定会判断是否满足，直接当成永远成立吧。）

势能函数

目的是求解一个随机过程（应该不需要是鞅）的停时的期望 \mathbb E(\tau)。

构造一个势能函数 \Phi(X)，满足：

人话就是势能函数每次期望 -1，停止时到达一个常数。
（其实没有理解为什么有第三条？防止 i 被误认为是停时？但是不知道为什么这样被误认会有问题（

然后由于期望的线性性，裂项就（应该？）得到了 \mathbb E(\tau)=\mathbb E(\Phi(X_0))-\Phi(X_\tau)。停时的期望就转化成了势能函数的期望。所以我们需要做的就是确定一个美好的势能函数然后竭尽全力计算其初态的期望。

link

以下设 s 为球的总数，c_i 为颜色为 i 的球的数量。

对于当前这道题，S 表示球的颜色状态，如果让势能函数 \Phi(S)=\sum f(c_i)，其中 f 是某个函数， c_i 是颜色为 i 的球的个数，则终止状态的势能函数值自然全相同。

因为期望的可加性，可直接考虑单个 f(c) 转移一次得到的东西的期望：

分别讨论了用当前颜色覆盖另一颜色的球，用另一颜色覆盖当前颜色的球，两个球都是/都不是当前颜色的情况。

设箭头右边的一坨为 f'(c)。然后我们需要让 F(S) 转移一次期望 -1，所以即对于任意 \sum c_i=s 的 \{c\}，都有\sum(f(c_i)-f'(c_i))=1。f'(c) 只能为 f(c)-\frac{c}{s}。

回到上面超长的柿子，把等式套进去解，得到

设 d(c)=f(c+1)-f(c)，则改写成 d(c)=d(c-1)-\frac{s-1}{s-c}。

规定 f(0)=0,d(0)=-1，然后快乐地递推就可以得到每一个 f(c_i) 了。现在还需要求 f(s)。

做完辣。

link

还是记 \Phi(S)=\sum f(s_i)。设一次操作选择了 x 个颜色 s_i 的球，y 个颜色不是 s_i 的球。发生的概率为 \frac{\binom{s_i}{x}\binom{n-s_i}{y}}{2^n}。将一个被选中的球染成 s_i 的概率为 \frac{x+y}{n}。于是我们可以得到下式：

（我知道你很急但你先别急（

然后因为对于所有 s_i 的组合都应成立所以 i 的求和可以削去。（并把 -1 变成 \sum_{i=1}^n \frac{s_i}{n} 的形式。）

省略下标 i，直接记 s_i=s，变换然后把混在一起的变量分开一下：

然后你知道 \sum_{i=0}^n\binom ni=2^n,\sum_{i=0}^ni\binom ni=(n-1)2^{n-1}，于是框起来的部分就无了。

具体地，第一行的尾巴是 (n+2x-s)2^{n-s-1}，第二行的尾巴是 (n-2x+s)2^{n-s-1}。

回代整理可得：

然后你要把和式里面的 f(s+1) 单拎出来因为这才是你想求的：（顺便，x'\leftarrow s-x）

大概是这个东西吧。可能。O(n^2)。

PGF

我们设 F(x)=\sum_c P(X=c)x^c，则 F'(1)=\sum_c P(X=c)\cdot c=\mathbb{E}(X)。

先规定一些记号：fix(i)=\left(\frac1n\right)^i， S(i) 表示一个长为 i 的字符串，[border(i)] 指示 A[1:i] 是否是 A 的 border。