（Ⅱ）工业制 wxr 实验记录

wxr_ · 2024-12-12 18:20:26 · 个人记录

Week 20

An empty street, an empty house
A hole inside my heart
I'm all alone, the rooms are getting smaller
I wonder how, I wonder why
I wonder where they are
The days we had, the songs we sang together
Oh yeah
And oh, my love
I'm holding on forever
Reaching for the love that seems so far
So I say a little prayer
And hope my dreams will take me there
Where the skies are blue
To see you once again, my love
Overseas from coast to coast
To find a place I love the most
Where the fields are green
To see you once again, my love
I try to read, I go to work
I'm laughing with my friends
But I can't stop, to keep myself from thinking, oh no
I wonder how, I wonder why
I wonder where they are
The days we had the songs, we sang together
Oh yeah
And oh, my love
I'm holding on forever
Reaching for the love that seems so far
So I say a little prayer
And hope my dreams will take me there
Where the skies are blue
To see you once again, my love
Overseas from coast to coast
To find a place I love the most
Where the fields are green
To see you once again
To hold you in my arms
To promise you my love
To tell you from the heart
You're all I'm thinking of
I'm reaching for the love that seem so far
So I say a little prayer
And hope my dreams will take me there
Where the skies are blue
To see you once again, my love
Overseas from coast to coast
To find a place I love the most
Where the fields are green
To see you once again (My love)
Say a little prayer
My sweet love
Dreams will take me there
Where the skies are blue
To see you once again (Oh, my love)
Overseas from coast to coast
To find a place I love the most
Where the fields are green
To see you once again, my love

12.9 NOIP 补题

首先，由 \text{dep}_{\text{LCA*}(l, r)} = \min\limits_{i = l}^{r - 1}{\text{dep}_{\text{lca}(i, i + 1)}}(l \ne r) 把区间 \text{lca} 转为区间 \min。

然后发现外层一个 \max 内层一个 \min 不好维护，二分再数据结构至少 \log^2，所以用笛卡尔树把 \min 转成 \max（详见上一篇的笛卡尔树部分），就可以扫描线 \log 维护。

12.10 最大流

helang 的讲课风格主打一个注重实现。

反正网络流板子确实是能用就行。

虽然不会证，但想到至今没学会 Tarjan 也就释然了。

Tarjan、二分图、2-SAT 之类图论建模其实现上的原理好像确实不太重要。

多路增广，当前弧优化，GAP 优化。

具体哪些是优化复杂度哪些是优化常数我也不好说，毕竟在玄学下常数也算复杂度的一部分。

根据相关法律法规，网络流题是不会卡 Dinic 的，但是 ISAP 是可以卡的。

近线性网络流：https://arxiv.org/abs/2203.00671

网络流模型的本质是反悔贪心。

我们有 \sum = \sum 以及 \le。

P2472：

对于「任何时刻不能有两只蜥蜴在同一个石柱上」这个限制，因为无法用网络流处理，所以不难猜到它是无效的。

其实是因为 P1007。

网络流的本质是 P1007。

P2891、UVA1324、P3163。

https://www.luogu.com/article/51f2i30j

有点抽象，但是很有道理。

这是一条两个方向共用一个流量的双向边，所以只能单向通过。

12.14 集训队互测 #3

T1 诈骗题，致敬 WPOI。

T2 比 T3 难，致敬 WPOI。

T3 数学题，致敬 WPOI。

T4 数据结构题，致敬 WPOI。

Week 21

12.16 AC 自动机

Aho-Corasick Deterministic Finite Automaton。

因为一个字符串的子串是它的一个前缀的后缀，所以我们开一个字典树维护前缀，再在字典树上开一个失配树维护后缀。

具体地，对于一个字符串，要查询其所有子串，就枚举其前缀，其子串就是这个前缀的后缀，即失配树上这个前缀对应的节点到根的路径；如果是所有本质不同子串，则会在失配树上构成一棵以根为根的虚树。

值得注意的是，失配树是棵树。

CF697F：一眼倍增。然而并没有一眼想到。

CF547E、P5840：在失配树上倒一倒发现是一个数据结构题，树剖随便维护。

12.18 最小割

网络中的割定义为某些边的集合，使得将这些边删除后可以使得源点到汇点不连通，即任意源点到汇点的路径上都至少有一条边被选择，即将网络划分为源点所在集合和汇点所在集合。集合中边的总容量最小的为最小割。

易证最小割容量等于最大流流量。

特别地，如果有 u \to v 的容量为 \infty，那么这条边不能从源点集合正向穿过割到达汇点集合。

P2774、P3756：

不需要染色就可以直接注意到每一个不能同时取的形式都可以映射为网络图上源点到汇点的一条路径，那么最优方案即为最小割。

P3227、P6054。

https://www.luogu.com/article/51f2i30j

有点抽象，但是很有道理。

相当于把 1 和 2 缩成一个点，所以可以对 1 和 2 在同一集合时计算收益。本质是最大权闭合子图。

这个东西的合理之处在于最小割可以计算两点在不同集合时的代价和在相同集合时的收益。两个分开说是因为这两个都必须是正的。

然后最大割是 NPC 的。闭环了。

扩展一下，就可以有如下题目：

有 n 个变量，a_i \in \{0, 1\}。

有 m 个条件，形如：

若 a_l, a_{l + 1} \cdots a_r 取值都为 k 则有 w 的收益。
若 a_{i_1}, a_{i_2} \cdots a_{i_j} 取值都为 k 则有 w 的收益。

求最大收益。

无向平面图最小割等于其对偶图最短路。

P4001。

12.21 集训队互测 #4

虽然又一次被数据结构题伤透了心，但是好题。

四场模拟赛中除了第二场的个别题目外都是好题。

Week 22

12.23 BSGS

本质上是类似于整体二分的对值域分块。即对于值域 V 以内的问题，将其分为 \sqrt{V} 块，再遍历每一块并判定答案是否在这个块中。

数论中用于离散对数问题和光速幂。

值得注意的是，如果底数和模数一定，那么求 n 次离散对数是 \sqrt{n P} 的。

12.23 阶和原根

对于 \gcd(a, m) = 1，使得 a^x \equiv 1 \pmod m 成立的最小正整数 x 为 a 模 m 的阶，记作 \delta_m (a) 或 \text{ord}_m a。

如果 x \bmod \delta(a) \not = 0，则有 a^{x \bmod \delta(a)} \equiv 1 \pmod m 且 x \bmod \delta(a) < \delta(a)，矛盾。

如果 (a ^ k) ^ x \equiv 1 \pmod m，则有 \delta(a) \mid k x。

那么使得 \delta(a) \mid k x 的最小 x = \dfrac{\delta(a)}{\gcd(\delta(a), k)} 即为 \delta(a ^ k)。

若 \delta(g) = \varphi(m)，则称 g 为模 m 的原根。

然后设 \text{ind}_g a 为使得 g^i \equiv a \pmod m 的 i，就有 a \cdot b = g^{\text{ind}_g a} \cdot g^{\text{ind}_g b} = g^{\text{ind}_g a + \text{ind}_g b} 了。

若 m 存在原根，则原根个数为 \varphi(\varphi(m))。

因为 \gcd(g', m) = 1，所以 g' = g ^ k。

又因为 \delta(g ^ k) = \dfrac{\delta(g)}{\gcd(\delta(g), k)} = \dfrac{\varphi(m)}{\gcd(\varphi(m), k)} = \varphi(m)，所以 \gcd(\varphi(m), k) = 1，k 共有 \varphi(\varphi(m)) 种取值。

12.25 最大权闭合子图

每个点被选择时有正或负的贡献，相当于正权点不被选择时有代价，负权点被选择时有代价。

然后就可以求最大权闭合子图，即每个点被选择后必须选择从其出发可以到达的点。

P3749。

12.26 费用流

能用费用流建模首先一定是凸的。

比如说选了特定数量个之后有一个额外贡献就大概率不行。

在流量最大的情况下使得费用最小，可以每次取最短路进行增广，但是要保证原图没有负环。显然做不到每一次把一条边容量取满，所以复杂度是基于值域的 O(nmf)。

多路增广的写法记得判零环。

可以构造图的同时构造最大流。

也可以只用网络流限制流量，不保证最大流只保证费用最小。

P1251：

发现用完的餐巾如果要同时用于统计和清洗，就不好用网络流处理。但是本题会有时间维度，所以可以假定今天之前的餐巾已经满足了再去处理今天的。

我们通过最大流保证每天需要的餐巾数量。

而每天需要的餐巾有两种来源。

直接购买。

清洗某天用过的餐巾。第 i 天可用于清洗的餐巾来源于第 i 天用完的餐巾和前 i - 1 天用完且未被清洗的餐巾。

P2469 同理。

BZOJ4261、P4003：

大概就是考虑水管连通时相邻网格的接口是对齐的。

P3358、P3980：

链式建图（？）

天天说什么链式建图，建分层图，先建源点和汇点的看着就不太会网络流。

实际上第一个是后缀优化建图。

第二个是通过总流量和优先边流量之差限制非优先边流量的下界，所以理论上可以直接上下界费用流。

Gym-105677J：

值得注意的是，没有环时，代价可以是负的，即不经其流过时有代价。

12.26 冬季环校跑

12.28 组队赛

12.28 年终总结

https://www.luogu.com.cn/article/2bwwt2hn

竞赛新锐！！！1

Week 23

12.30 元旦晚会

12.31 课前三分钟

人渣的本愿，苏联的解体。

12.31 Miller–Rabin 素性测试

~~板子，不解释。~~

忘记了。

首先有费马小定理 (\forall~p \in \mathbb{P})~~a^{p - 1} \equiv 1 \pmod p。

然后有二次探测定理 (\forall~p \in \mathbb{P} \setminus \{2\})~~x^2 \equiv 1 \pmod p \implies x \equiv \pm 1 \pmod p。

这样取前 12 个素数就可以判定 2^{64}。

bool millerrabin(long long n)
{
    if (n < 2 || n % 2 == 0) return n == 2;
    long long t = n - 1;
    while (t % 2 == 0) t /= 2;
    for (long long p : {2, 325, 9375, 28178, 450775, 9780504, 1795265022})
    {
        if ((p %= n) == 0) continue;
        if (qpow(p, n - 1, n) != 1) return 0;
        for (long long x = qpow(p, t, n), y; x != 1; x = y)
        {
            y = (long long)((__int128)x * x % n);
            if (y == 1 && x != 1 && x != n - 1) return 0;
        }
    }
    return 1;
}

12.31 有效应对压力，拥抱多彩青春期

1.1 元旦晚会

Lately I've been, I've been losing sleep
Dreaming 'bout the things that we could be
But baby, I've been, I've been praying hard
Said no more counting dollars
We'll be counting stars
Yeah, we'll be counting stars
I see this life
Like a swinging vine
Swing my heart across the line
In my face is flashing signs
Seek it out and ye shall find
Old, but I'm not that old
Young, but I'm not that bold
And I don't think the world is sold
I'm just doing what we're told
I, feel something so right
But doing the wrong thing
I, feel something so wrong
But doing the right thing
I could lie, could lie, could lie
Everything that kills me makes me feel alive
Lately I've been, I've been losing sleep
Dreaming 'bout the things that we could be
Baby I've been, I've been prayin' hard
Said no more counting dollars
We'll be counting stars
Lately I've been, I've been losing sleep
Dreaming 'bout the things that we could be
Baby I've been, I've been prayin' hard
Said no more counting dollars
We'll be, we'll be counting stars
I feel the love
And I feel it burn
Down this river every turn
Hope is a four letter word
Make that money
Watch it burn
Old, but I'm not that old
Young, but I'm not that bold
And I don't think the world is sold
I'm just doing what we're told
I, feel something so wrong
But doing the right thing
I could lie, could lie, could lie
Everything that drowns me makes me wanna fly
Lately I've been losing sleep
Dreaming 'bout the things that we could be
Baby I've been, I've been prayin' hard
Said no more counting dollars
We'll be counting stars
Lately I've been, I've been losing sleep
Dreaming 'bout the things that we could be
Baby I've been, I've been prayin' hard
Said no more counting dollars
We'll be, we'll be counting stars
Take that money
And watch it burn
Sink in the river
The lessons I learnt
Take that money
And watch it burn
Sink in the river
The lessons I learnt
Take that money
And watch it burn
Sink in the river
The lessons I learnt
Take that money
And watch it burn
Sink in the river
The lessons I learnt
Everything that kills me makes me feel alive
Lately I've been, I've been losing sleep
Dreaming 'bout the things that we could be
Baby I've been, I've been prayin' hard
Said no more counting dollars
We'll be counting stars
Take that money
And watch it burn
Sink in the river
The lessons I learnt
Take that money
And watch it burn
Sink in the river
The lessons I learnt
Take that money
And watch it burn
Sink in the river
The lessons I learnt
Take that money
And watch it burn
Sink in the river
The lessons I learnt

故事的小黄花
从出生那年就飘着
童年的荡秋千
随记忆一直晃到现在
Re So So Si Do Si La
So La Si Si Si Si La Si La So
吹着前奏 望着天空
我想起花瓣试着掉落
为你翘课的那一天
花落的那一天
教室的那一间
我怎么看不见
消失的下雨天
我好想再淋一遍
没想到 失去的勇气我还留着
好想再问一遍
你会等待还是离开
刮风这天 我试过握着你手
但偏偏 雨渐渐
大到我看你不见
还要多久 我才能在你身边
等到放晴的那天
也许我会比较好一点
从前从前 有个人爱你很久
但偏偏 风渐渐
把距离吹得好远
好不容易 又能再多爱一天
但故事的最后
你好像还是说了 拜拜
为你翘课的那一天
花落的那一天
教室的那一间
我怎么看不见
消失的下雨天
我好想再淋一遍
没想到 失去的勇气我还留着
好想再问一遍
你会等待还是离开
刮风这天 我试过握着你手
但偏偏 雨渐渐
大到我看你不见
还要多久 我才能在你身边
等到放晴的那天
也许我会比较好一点
从前从前 有个人爱你很久
偏偏 风渐渐
把距离吹得好远
好不容易 又能再多爱一天
但故事的最后
你好像还是说了 拜拜
刮风这天 我试过握着你手
但偏偏 雨渐渐
大到我看你不见
还要多久 我才能够在你身边
等到放晴那天
也许我会比较好一点
从前从前 有个人爱你很久
但偏偏 雨渐渐
把距离吹得好远
好不容易 又能再多爱一天
但故事的最后
你好像还是说了拜

1.2 分数规划

值得注意的是，如果只要求 \max\limits_{w_i \in \{0, 1\}}\{\dfrac{\sum p_i \cdot w_i}{\sum q_i \cdot w_i}\}，那么答案其实就是 \max\limits_{i}\{\dfrac{p_i}{q_i}\}，并不用二分。

1.3 Pollard Rho

~~板子，不解释。~~

也忘了。

考虑生日悖论，对于合数 n 的最小素因子 p，随机期望长度 \sqrt{p} \le n^{\frac{1}{4}} 的序列可以使得其中存在两个数模 p 同余。

那么构造随机函数 f(x) = (x^2 + c) \bmod n，如果有 x \equiv y \pmod p，也有 f(x) \equiv f(y) \pmod p。

这样就形成了 [0, p) 每个点出边为 x \to ( f(x) \bmod p ) 的内向基环树森林。从某个点出发，期望迭代 \sqrt{p} 次到达环上并绕环一圈。

使用 Floyd 判环法，从同一点 a = b = x 出发，每次迭代 a \gets f(a)，b \gets f(f(b))。设 x 到环上距离为 l，环长为 c，E(l + c) = \sqrt{p} ，迭代 c \cdot \left\lceil \dfrac{l}{c} \right\rceil < l + c 次两者到达同一点时，p \mid a - b，以 \gcd(n, a - b) 更新答案。

struct pollardrho
{
    std::vector<long long> res;
    std::mt19937_64 rand;
    void rho(long long n)
    {
        if (n == 4) return res.push_back(2), res.push_back(2);
        if (millerrabin(n)) return res.push_back(n);
        long long t = 1, cnt = 0;
        #define rng(x) (long long)(((__int128)(x) * (x) + k) % n)
        for (long long st = rand() % n, k = rand() % n, x = rng(st), y = rng(rng(st)); x != y; x = rng(x), y = rng(rng(y)))
        {
            t = (t = (long long)((__int128)t * std::abs(x - y) % n)) == 0 ? 1 : t, cnt++;
            if (cnt == (cnt >> 7 << 7) || cnt == (cnt & -cnt))
            {
                long long g = std::__gcd(t, n);
                if (1 < g && g < n) return rho(g), rho(n / g);
                t = 1;
            }
        }
        #undef rng
        long long g = std::__gcd(t, n);
        if (1 < g && g < n) return rho(g), rho(n / g);
        return rho(n);
    }
    auto operator () (long long n) { return res.clear(), rho(n), std::sort(res.begin(), res.end()), res; }
}
pollardrho;

I'm sitting here in the boring room
It's just another rainy Sunday afternoon
I'm wasting my time I got nothing to do
I'm hanging around I'm waiting for you
But nothing ever happens and I wonder
I'm driving around in my car
I'm driving too fast I'm driving too far
I'd like to change my point of view
I feel so lonely I'm waiting for you
But nothing ever happens and I wonder
I wonder how I wonder why
Yesterday you told me about the blue blue sky
And all that I can see is just a yellow lemon tree
I'm turning my head up and down
I'm turning turning turning turning turning around
And all that I can see is just another lemon tree
I'm sitting here I miss the power
I'd like to go out taking a shower
But there's a heavy cloud inside my head
I feel so tired put myself into bed
Where nothing ever happens and I wonder
Isolation is not good for me
Isolation I don't want to sit on the lemon tree
I'm stepping around in the desert of joy
Baby anyhow I'll get another toy
And everything will happen and you'll wonder
I wonder how I wonder why
Yesterday you told me about the blue blue sky
And all that I can see is just another lemon tree
I'm turning my head up and down
I'm turning turning turning turning turning around
And all that I can see
Is just a yellow lemon tree
And I wonder wonder
I wonder how I wonder why
Yesterday you told me about the blue blue sky
And all that I can see
And all that I can see
And all that I can see
Is just a yellow lemon tree

1.4 二次剩余

引入 Legendre 符号表示 a 是否是 p 的二次剩余

\left(\frac{a}{p}\right)= \begin{cases} 0, & p\mid a,\\ 1, & (p\nmid a) \land ((\exists x\in\mathbf{Z}),~~a\equiv x^2\pmod p),\\ -1, & \text{otherwise}.\\ \end{cases}

注意到 \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p。

所以 Legendre 有完全积性，即 \left(\frac{ab}{p}\right) = a^{\frac{p-1}{2}} b^{\frac{p-1}{2}} = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)。

二次互反律：\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}。非常的好，但我不会。

从另一个角度来说，原根的偶次幂是二次剩余，奇次幂是非二次剩余。

仅考虑 p 为奇素数的情况。其他情况分讨一下再 exCRT 合并一下就行了。反正不会考。

Cipolla～(∠・ω< )⌒★

随机 b 使得 \omega \equiv b ^ 2 - a \pmod p 为二次非剩余。这个概率应当是 \dfrac{1}{2}。不是也没办法。

然后设 i ^ 2 \equiv \omega \pmod p。

那么就可以用惊人的注意力发现 (b + i) ^ {\frac{p + 1}{2}} 为 a 的二次剩余。

首先，因为 \omega 为二次非剩余，所以 \omega^{\frac{p - 1}{2}} \equiv i^{p - 1} \equiv -1 \pmod p，那么 i ^ p \equiv -i \pmod p。

\begin{aligned} & \left((b + i) ^ {\frac{p + 1}{2}}\right) ^ 2 \\ \equiv & (b + i) ^ {p + 1} \\ \equiv & (b + i) ^ p \cdot (b + i)\\ \equiv & (\sum\limits_{j = 0}^p \binom{p}{j} b^j i^{p - j}) \cdot (b + i) \\ \equiv & (b ^ p + i ^ p) \cdot (b + i) \\ \equiv & (b - i) \cdot (b + i) \\ \equiv & b ^ 2 - i ^ 2 \\ \equiv & a \\ \end{aligned}

其中 \dbinom{p}{j} \bmod p 在 p 为质数时当且仅当 j = 0 或 j = p 时有取值。

然后再证一下 (b + i) ^ {\frac{p + 1}{2}} 的虚部为 0：

设 (b + i) ^ {\frac{p + 1}{2}} = x + y \mathrm{i} (y \neq 0)，那么 (x + y \mathrm{i}) ^ 2 的虚部为 2xy\mathrm{i} = 0，则有 x = 0，得到 y ^ 2 \omega = a。y ^ 2 是二次剩余，\omega 是非二次剩余，a 是二次剩余，矛盾。

1.4 二阶递推与斐波那契数列

二阶常系数齐次线性递推。

f_n = \begin{cases} a, & n = 1,\\ b, & n = 2,\\ x \cdot f_{n - 1} + y \cdot f_{n - 2}, & \text{otherwise}.\\ \end{cases}

集中注意力，不难注意到 \dfrac{f_n - p f_{n - 1}}{f_{n - 1} - p f_{n - 2}} = q。

化简得 f_n = (p + q) f_{n - 1} - pq f_{n - 2}。

由 $ \begin{cases} p + q = x \ -pq = y \ \end{cases}

，解得

\begin{cases} p_1 = \dfrac{x + \sqrt{x ^ 2 + 4y}}{2} \ q_1 = \dfrac{x - \sqrt{x ^ 2 + 4y}}{2} \ \end{cases}

，

\begin{cases} p_2 = \dfrac{x - \sqrt{x ^ 2 + 4y}}{2} \ q_2 = \dfrac{x + \sqrt{x ^ 2 + 4y}}{2} \ \end{cases}

将 $p_1, q_1$ 代入得 $$f_{n + 1} - \dfrac{x + \sqrt{x ^ 2 + 4y}}{2} f_n = \left(\dfrac{x - \sqrt{x ^ 2 + 4y}}{2}\right) ^{n - 1} \left( b - \dfrac{x + \sqrt{x ^ 2 + 4y}}{2} a \right)$$ 将 $p_2, q_2$ 代入得 $$f_{n + 1} - \dfrac{x - \sqrt{x ^ 2 + 4y}}{2} f_n = \left(\dfrac{x + \sqrt{x ^ 2 + 4y}}{2}\right) ^{n - 1} \left( b - \dfrac{x - \sqrt{x ^ 2 + 4y}}{2} a \right)$$ 联立两方程解得 $$ f_n = \dfrac{1}{\sqrt{x ^ 2 + 4y}} \left( \left(\dfrac{x + \sqrt{x ^ 2 + 4y}}{2}\right) ^{n - 1} \left(\dfrac{2b - ax + a \sqrt{x ^ 2 + 4y}}{2} \right) - \left(\dfrac{x - \sqrt{x ^ 2 + 4y}}{2}\right) ^{n - 1} \left(\dfrac{2b - ax - a \sqrt{x ^ 2 + 4y}}{2} \right) \right) $$ 代入 $a = b = x = y = 1$，得斐波那契通项公式 $$ F_n = \dfrac{1}{\sqrt{5}} \left( \left(\dfrac{1 + \sqrt{5}}{2}\right) ^ n - \left(\dfrac{1 - \sqrt{5}}{2}\right) ^ n \right) $$ 设 $\phi = \dfrac{1 + \sqrt{5}}{2}$，$\hat\phi = \dfrac{1 - \sqrt{5}}{2}$。有 $\phi \cdot \hat\phi = -1$，$\phi + \hat\phi = 1$，$\phi ^ 2 = \phi + 1$，$\hat\phi ^ 2 = \hat\phi + 1$。 --- 对此，大哲♂学家 @nb_jzy 提出辩证： > 为什么斐波那契有通项公式？证明。如果斐波那契数列有通项公式，世界上的万事万物是否都有通项公式？我们能否通过无限的信息从理论上推理出下一秒会发生什么，仅仅凭借一个通项公式？你写的网络流是通项公式吗？ > > 通项公式是不是和预制菜一个道理？用通项公式算出的斐波那契数列和矩阵快速幂推出的斐波那契数列和递推出的斐波那契数列是否相同？这本质上是一个推修四之船的问题，如果解决问题的方法发生变化，那你解决的还是同一个问题吗？ > > **通项公式只是一种投机取巧的方法罢了，你根本不明白递推带给人们的乐趣**。虽然不知道他是什么意思，但感觉很有这里。 --- 可以注意力涣散地注意到斐波那契的循环节不超过 $m ^ 2$。但是集中注意力可以发现更好的上界 $6m$。在模数为质数的情况下，若 $5$ 是二次剩余，周期为 $p - 1$ 的因数；若 $5$ 是非二次剩余，周期为 $2p + 2$ 的因数。lwc 说的，不知道为什么。 --- OI Wiki 上还给出了斐波那契数列的一些简单的性质： - $F_{n - 1}F_{n + 1} - F_n^2 = (-1)^n

F_{n + m} = F_n F_{m - 1} + F_{n + 1} F_m
\gcd(F_n, F_m) = F_{\gcd(n, m)}

但仔细考虑后会发现这并不显然。建议放到数学选择压轴。@luoyudong

第一个代入通项公式暴算可证。

第二个大约也可以代入通项公式，但可以归纳法证。

当 m \le 2 时，显然成立。

当 m = k 时

F_{n + k - 1} = F_n F_{k - 2} + F_{n + 1} F_{k - 1} \\ F_{n + k} = F_n F_{k - 1} + F_{n + 1} F_k

两式相加，得

\begin{aligned} F_{n + k + 1} = & F_n F_{k - 2} + F_{n + 1} F_{k - 1} + F_n F_{k - 1} + F_{n + 1} F_k \\ = & F_n (F_{k - 2} + F_{k - 1}) + F_{n + 1} (F_{k - 1} + F_{k}) \\ = & F_n F_k + F_{n + 1} F_{k + 1} \\ \end{aligned}

把那个式子换元，得到 F_{m} = F_n F_{m - n - 1} + F_{n + 1} F_{m - n}。

所以

\begin{aligned} \gcd(F_n, F_m) = & \gcd(F_n, F_n F_{m - n - 1} + F_{n + 1} F_{m - n}) \\ = & \gcd(F_n, F_{n + 1} F_{m - n}) \\ = & \gcd(F_n, F_{m - n}) \\ = & \gcd(F_{n}, F_{m \bmod n}) \\ = & F_{\gcd(n, m)} \\ \end{aligned}

反正就是辗转相除法。

Week 24

1.7

int _a[maxn * 2], *const a = _a + maxn;

负数下标语法唐。

1.8 模拟费用流

WC2019《模拟费用流问题》课件

模拟费用流是在费用流的建模下考虑用反悔贪心和数据结构模拟费用流。

静态求解费用流的 SSP 正确性基于每次增广都优先取最短路。不会反悔与源点或汇点相邻的边。

对于模拟 SSP 的模拟费用流，考虑用线段树等数据结构维护当前图中的最短路。

动态求解费用流的消圈在图中不断寻找负环并将其消去。可能反悔与源点或汇点相邻的边。

对于模拟消圈的模拟费用流，考虑每次加边后在形成的从源点到汇点的负路径和图中的负环。

模拟费用流一般不要求流量最大，只要求费用最小。

所以可以先连一条源点到汇点容量为 \infty 费用为 0 的边，然后动态加流量。

~~费用流中最短路的长度会不断增长，所以费用是关于流量的凸函数，就可以 wqs 二分。~~

BZOJ4997：

从左到右枚举，考虑新增的一个人。新增房子不会有贡献。

红边是新增边，黑边是原边，不能确定方向。

人肉在图中寻找增广路或负环。

实际意义为直接进入某个空房子。

实际意义为让某个房子中的人出去，自己进去。

实际意义为让某个房子中的人换一个房子，自己进去。但是可以发现这种情况和自己直接进换的那个房子等价，不用考虑。

UOJ455：

看似只是将上一道题改成了双向行走，然后只需要对于房子再讨论一下就行了。

但如果仅止于此的话这道题就不会 dv446 了。

~~没有笑点解析。~~

笑点解析：

关于该猜想，我们并没能给出证明或反例(基于对拍认为该猜想有较大概率正确)。如果能在WC之前证明做法的正确性或者举出反例的同学可以在WC中获得出题人提供的小礼品一份。

P3620、CF280D、P6122、P4694、P9168。

还有一道可以模拟费用流的不得不提的反悔贪心传奇题目 P3045。

值得注意的是，还可以模拟最大流（CF1895G）、模拟最小割（CF724E）。

1.9

逆天结论在 n \le 1000 时成立所以就可做？？？

1.10 矩阵的初等变换、逆、秩

任意矩阵乘以满秩矩阵，秩不改变。
𝑟𝑎𝑛𝑘(𝐴 + 𝐵) ≤ 𝑟𝑎𝑛𝑘(𝐴) + 𝑟𝑎𝑛𝑘(𝐵)
max(𝑟𝑎𝑛𝑘(𝐴), 𝑟𝑎𝑛𝑘(𝐵)) ≤ 𝑟𝑎𝑛𝑘([𝐴 | 𝐵]) ≤ 𝑟𝑎𝑛𝑘(𝐴) + 𝑟𝑎𝑛𝑘(𝐵)
𝑟𝑎𝑛𝑘(𝐴𝐵) ≤ min(𝑟𝑎𝑛𝑘(𝐴), 𝑟𝑎𝑛𝑘(𝐵))

读者自证不难，但是我一个都不会证，摆了。

1.11 行列式

主要用于 Matrix-Tree 、LGV、化学竞赛和数学选择压轴。

交换两行，逆序对奇偶全部改变，行列式乘 -1。

若有两行相同，交换后乘 -1 且不变，行列式为 0。

一行同乘 k，可以提到外面，行列式乘 k。

一行加上另一行，展开得到行列式加上一个两行相同的行列式，行列式不变。

Week 25

期末考试

！！！1

Day 1.0（1.14 a.m.）

语文。

Day 1.5（1.14 p.m.）

物理化学。

Day 1.9

破防了。

你们都是强者，那当然是一笑置之了。可是我啊，我听破防了啊！

含金量仍在提升。

Day 2.0（1.15 a.m.）

数学。

Day 2.5（1.15 p.m.）

政治历史。

Day 3.0（1.16 a.m.）

英语。

Day 3.4

脊椎动物.mp4。

以父之名、止战之殇、她的睫毛、晴天。

Day 5（1.18）

512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 
512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB 512MB

Week 26

1.20 数论函数

狄利克雷卷积、积性函数、莫比乌斯函数。

\mu \xrightleftharpoons[* \mu]{* 1} \varepsilon \xrightleftharpoons[* \mu]{* 1} 1 \xrightleftharpoons[* \mu]{* 1} d

\varphi \xrightleftharpoons[* \mu]{* 1} \operatorname{id} \xrightleftharpoons[* \mu]{* 1} \sigma

\mu(ij) = \mu(i)\mu(j)[\gcd(i, j) = 1]

\varphi(ij) = \dfrac{\varphi(i)\varphi(j)\gcd(i, j)}{\varphi(\gcd(i, j))}

d(ij) = \sigma_{0}(ij) = \sum_{x | i}\sum_{y | j} [\gcd(x, y) = 1]

\sigma_{k}(n m) = \sum_{x | n}\sum_{y | m} [\gcd(x, y) = 1] \left( x \cdot \dfrac{m}{y} \right) ^ k

证明：https://www.luogu.com/article/7illuooi

\begin{aligned} & \sigma_{k}(nm) \\ = & \sigma_{k}(\prod_{t}^n p_t^{x_t} p_t^{y_t}) \\ = & \prod_{t}^n \sigma_{k}(p_t^{x_t} p_t^{y_t}) \\ = & \prod_{t}^n \sum_{d | p_t^{x_t + y_t}} d ^ k \\ = & \prod_{t}^n \sum_{i = 0}^{x_t + y_t} p_t ^ {ik} \\ = & \prod_{t}^n \sum_{i = 0}^{x_t} \sum_{j = 0}^{y_t} [\min(i, j) = 0] p_t^{(x_t - i)k} p_t^{jk} \\ = & \prod_{t}^n \sum_{i = 0}^{x_t} \sum_{j = 0}^{y_t} [\min(i, j) = 0] \left( \dfrac{p_t^{x_t} p_t^{j}}{p_t^{i}} \right) ^ k \\ = & \sum_{a | n}\sum_{b | m} [\gcd(a, b) = 1] \left( \dfrac{n b}{a} \right) ^ k \end{aligned}

1.21 莫比乌斯繁衍

欧拉繁衍。

\begin{cases} F(n) = \sum_{d | n} f(d) \iff f(n) = \sum_{d | n} \mu\left(\dfrac{n}{d}\right) F(d) \\ F(n) = \sum_{n | d} f(d) \iff f(n) = \sum_{n | d} \mu\left(\dfrac{d}{n}\right) F(d) \\ \varepsilon(n) = [n = 1] = \sum_{d | n} \mu(d) \end{cases}

前两个式子说明了莫比乌斯函数是以每个质数为维度的高维前后缀和中差分时的容斥系数。

但鉴于除了 @nb_jzy 以外的绝大多数人都只能想象到三维空间，所以？？？？、？？？？？？、、？

被 hyy 几餐了、、、

然后高维前后缀和复杂度同埃筛，\sum\limits_{p \in \mathbb{P}} \dfrac{n}{p} 为 O(n \log \log n)。

因为 \pi(n) \sim \dfrac{n}{\ln n}，\pi(n - 1) \sim \dfrac{n - 1}{\ln(n - 1)}，所以 n 是质数的概率约为 \dfrac{1}{\ln(n)}。那么复杂度就是 \sum\limits_{i = 1}^n \dfrac{1}{\ln i} \cdot \dfrac{n}{i} = n \ln \ln n。

而且卷积性函数都可以做到 O(n \log \log n)。

对于积性函数 f 设 f_p(n) = [n = p ^ k] f(n)，那么 f = f_2 * f_3 * f_5 * \cdots * f_{p_{\pi(n)}}。

如果 $f$ 和 $g$ 都是积性函数，那么 $f * g$ 也是积性函数，只需要求 $(f * g)(p ^ k)$，复杂度 $O(n)$。 --- 最后一个式子一般用来求类似 $$ \begin{aligned} & \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m f(\gcd(i, j)) \\ = & \sum\limits_g f(g) \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i, j) = g] \\ = & \sum\limits_g f(g) \sum\limits_{i = 1}^{\frac{n}{g}} \sum\limits_{j = 1}^{\frac{m}{g}} [\gcd(i, j) = 1] \\ = & \sum\limits_g f(g) \sum\limits_{i = 1}^{\frac{n}{g}} \sum\limits_{j = 1}^{\frac{m}{g}} \sum_{\substack{d | i \\ d | j}} \mu(d) \\ = & \sum\limits_g f(g) \sum\limits_d \mu(d) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor \\ = & \sum\limits_T \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d | T} f(d) \cdot \mu(\frac{T}{d}) \end{aligned} $$ 倒数第二个式子中 $\sum f$ 和 $\sum \mu$ 用杜教筛处理，$\lfloor \dfrac{n}{gd} \rfloor \lfloor \dfrac{m}{gd} \rfloor$ 用整除分块套整除分块处理，复杂度 $O(n ^ {\frac{3}{4}})

最后一个式子中 \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor 用整除分块处理，\sum (f * \mu) 用杜教筛处理，复杂度 O(n ^ {\frac{2}{3}})。

https://www.luogu.com/article/7wywbzvf

SP4168：

考虑容斥。

类似欧拉函数的求法把完全平方数的倍数容斥掉，容斥系数即为 \mu，再进行一个整除的分块后复杂度约为 O(n ^ {\frac{1}{3}})。

或者注意到 \mu^2(n) = \sum\limits_{i ^ 2 | n} \mu(i)。

设 f(n) = \max\{x ~\vert~ x | n \land x = k ^ 2 \land k \in \mathbb{Z} \}，即 n 的最大完全平方因数。

则有 \mu^2(n) = [f(n) = 1] = \sum\limits_{d | f(n)} \mu(d) = \sum\limits_{i ^ 2 | n} \mu(i)。

求 \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N \operatorname{lcm}(a_i, a_j) \ (N, a_i \le 10^7)。

考虑 gcd 卷积，设 f(n) = \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N a_i a_j[\gcd(a_i, a_j) = n]。

设 F(n) = \sum\limits_{i = 1}^N \sum\limits_{j = 1}^N a_i a_j[n | a_i, n | a_j] = \left( \sum\limits_{i = 1}^N a_i[n | a_i] \right) ^ 2。

则有 F(n) = \sum\limits_{n | d} f(d)。

那么 f(n) = \sum\limits_{n | d} \mu\left(\dfrac{d}{n}\right) F(d)。

just_int_mian 恒等式：

\begin{aligned} & \sum_{i = 1}^n i [\gcd(i, n) = 1] \\ = & \sum_{i = 1}^n i \sum_{d | i, d | n} \mu(d) \\ = & \sum_{d | n} \mu(d) \cdot d \sum_{i = 1}^{\frac{n}{d}} i \\ = & \sum_{d | n} \mu(d) \cdot d \cdot \frac{1}{2} \cdot \frac{n}{d} \cdot (\frac{n}{d} + 1) \\ = & \frac{n}{2} \sum_{d | n} \mu(d) \cdot (\frac{n}{d} + 1) \\ = & \frac{n}{2} \left( \left(\sum_{d | n} \mu(d) \frac{n}{d} \right) + \left(\sum_{d | n} \mu(d) \right) \right) \\ = & \frac{n}{2} \left( \varphi(n) + \varepsilon(n) \right) \\ \end{aligned}

组合意义天地灭，代数推导保平安。

组合意义是互质的数成对出现，共有 \dfrac{\varphi(n)}{2} 对，每对和为 n。

1.21 整除分块

\begin{aligned} & \left( \sum_{i = 1}^{\sqrt{n}} 2 \sqrt{i} \right) + \left( \sum_{i = 1}^{\sqrt{n}} 2 \sqrt{\dfrac{n}{i}} \right) \\ = & 2 \left( \sum_{i = 1}^{n ^ {\frac{1}{2}}} i ^ {\frac{1}{2}} \right) + 2 \cdot n ^ {\frac{1}{2}} \left( \sum_{i = 1}^{n ^ {\frac{1}{2}}} i ^ {-\frac{1}{2}} \right) \\ = & 2 \left( \dfrac{n^{\frac{1}{2} \cdot (\frac{1}{2} + 1)}}{\frac{1}{2} + 1} \right) + 2 \cdot n ^ {\frac{1}{2}} \left(\dfrac{n^{\frac{1}{2} \cdot (- \frac{1}{2} + 1)}}{- \frac{1}{2} + 1} \right) \\ = & \dfrac{16}{3} n^{\frac{3}{4}} \\ \end{aligned}

所以整除分块套整除分块的复杂度是 O(n ^ {\frac{3}{4}})。

如果内层可以线性预处理那也也能做到杜教筛的 O(n ^ {\frac{2}{3}})。

\begin{aligned} & \left( \sum_{i = 1}^{n ^ \frac{1}{2}} \dfrac{16}{3} i^{\frac{3}{4}} \right) + \left( \sum_{i = 1}^{n ^ \frac{1}{2}} \dfrac{16}{3} (\dfrac{n}{i}) ^ {\frac{3}{4}} \right) \\ = & \dfrac{16}{3} \left( \dfrac{n^{\frac{1}{2} \cdot (\frac{3}{4} + 1)}}{\frac{3}{4} + 1} \right) + \dfrac{16}{3} \cdot n ^ {\frac{3}{4}} \left(\dfrac{n^{\frac{1}{2} \cdot (- \frac{3}{4} + 1)}}{- \frac{3}{4} + 1} \right) \\ = & \dfrac{512}{21} n^{\frac{7}{8}} \\ \end{aligned}

--- $$ \begin{aligned} & \left\lfloor \dfrac{a}{bc} \right\rfloor \ (a, b, c \in \mathbb{Z})\\ = & \left\lfloor \dfrac{a}{b} \cdot \dfrac{1}{c} \right\rfloor \\ = & \left\lfloor \dfrac{kb + r}{b} \cdot \dfrac{1}{c} \right\rfloor \ (k \in \mathbb{Z}, r \in [0, b) \cap \mathbb{Z}) \\ = & \left\lfloor \dfrac{k + \frac{r}{b}}{c} \right\rfloor \\ \in & \left[ \left\lfloor \dfrac{k}{c} \right\rfloor, \left\lfloor \dfrac{k + 1}{c} \right\rfloor \right) \\ = & \left\lfloor \dfrac{k}{c} \right\rfloor \\ = & \left\lfloor \dfrac{ \lfloor \frac{a}{b} \rfloor }{c} \right\rfloor \\ \end{aligned} $$ --- P3327。 --- P3704： $$ \begin{aligned} & \prod_{i = 1}^n \prod_{j = 1}^m f_{\gcd(i, j)} \\ = & \prod_{g} f_{g} ^ {\sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = g]} \\ = & \prod_{g} f_{g} ^ {\sum_{d} \mu(d) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor} \\ = & \prod_{g} \prod_{d} f_{g} ^ {\mu(d) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor} \\ = & \prod_{g} \prod_{d} \left( f_{g} ^ {\mu(d)} \right) ^{\lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor} \\ = & \prod_{T} \left( \prod_{d | T} f_{d} ^ {\mu(\frac{T}{d})} \right) ^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor} \\ \end{aligned} $$ ## 1.22 Codeforces Round 1000 (Div. 2) https://codeforces.com/bestRatingChanges/16252970 ## 1.23 杜教筛对于数论函数 $f$，设 $F(n) = \sum_{i = 1}^n f(i)$，然后就有 $$ \begin{aligned} & \sum_{i = 1}^n (f * g)(i) \\ = & \sum_{i = 1}^n \sum_{d | i} g(d) f\left(\dfrac{i}{d}\right) \\ = & \sum_{d = 1}^n g(d) \sum_{i = 1}^{\frac{n}{d}} f(i) \\ = & \sum_{d = 1}^n g(d) F(\lfloor \dfrac{n}{d} \rfloor) \\ \end{aligned} $$ $$ g(1) F(n) = \left( \sum_{i = 1}^n (f * g)(i) \right) - \left( \sum_{d = 2}^n g(d) F(\lfloor \dfrac{n}{d} \rfloor) \right) $$ 如果可以快速求 $\sum(f * g)$ 和 $\sum g$ 就可以整除分块后求出所有 $\sum f(\lfloor \dfrac{n}{d} \rfloor)$ 的同时递归求出 $\sum f$。同时说明了如果能求 $\sum f$ 和 $\sum g$，那么 $\sum f * g$ 也可以整除分块求得。复杂度 $O(n^{\frac{3}{4}})$。如果能预处理那么复杂度为 $ T + \sum\limits_{i = 1}^{\frac{n}{T}} 2 \sqrt{\dfrac{n}{i}}$，令 $T = \sum\limits_{i = 1}^{\frac{n}{T}} 2 \sqrt{\dfrac{n}{i}} = 2 n^{\frac{1}{2}} \sum\limits_{i = 1}^{\frac{n}{T}} i ^ {-\frac{1}{2}} = 2 n^{\frac{1}{2}} \left( \dfrac{\left(\frac{n}{T}\right) ^ {1 - \frac{1}{2}}}{1 - \frac{1}{2}} \right) = 4 n T^{-\frac{1}{2}}$，则当 $T = (4n)^{\frac{2}{3}}$ 时有复杂度 $O(n ^ {\frac{2}{3}})$。 --- P3768： $$ \begin{aligned} & \sum_{i = 1}^n \sum_{j = 1}^n i j \gcd(i, j) \\ = & \sum_{i = 1}^n \sum_{j = 1}^n i j \sum_{\substack{d|i \\ d|j}}\varphi(d) \\ = & \sum_{d = 1}^n \varphi(d) \cdot d^2 \left( \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} i \right) ^ 2 \\ \end{aligned} $$ 记 $f(n) = \varphi(n) \cdot n ^ 2$，$s(n) = \dfrac{n^2(n + 1)^2}{4}$。即求 $\sum_{d = 1}^n f(n) \cdot s(\lfloor \frac{n}{d} \rfloor)$。对 $s(\lfloor \frac{n}{d} \rfloor)$ 整除分块后需要求 $\sum f$。构造 $g(n) = n^2$。则有 $(f * g)(n) = \sum\limits_{d | n} f(d) \cdot g\left(\dfrac{n}{d}\right) = \sum\limits_{d | n} \varphi(d) \cdot d^2 \cdot \left(\dfrac{n}{d}\right) ^ 2 = n ^ 2 \sum\limits_{d | n} \varphi(d) = n^3$。所以 $\sum g$ 和 $\sum f * g$ 都是好求的，就可以杜教筛。 --- LOJ6229：推一下式子发现求的是 $\sum\limits_{i = 1}^n \sum\limits_{j = 1}^{\frac{n}{i}} \mu(j) \cdot j ^ 2 \cdot \left(\sum\limits_{k = 1}^{\frac{n}{ij}}k\right) ^ 2$。分块套分块可以直接求，但是 NKOJ 过不去。再推一下式子发现求的是 $\sum\limits_{i = 1}^n \left( \sum\limits_{j = 1}^{\frac{n}{i}} j \right) ^ 2 \sum\limits_{d | i} \mu(d) \cdot d ^ 2$，需要筛 $1 * (\mu \cdot \operatorname{id}_2)$。卷上 $\operatorname{id}_2$ 得到 $1 * (\mu \cdot \operatorname{id}_2) * \operatorname{id}_2 = 1 * (\mu \cdot \operatorname{id}_2) * (1 \cdot \operatorname{id}_2) = 1 * ((\mu * 1) \cdot \operatorname{id}_2) = 1 * (\varepsilon \cdot \operatorname{id}_2) = 1 * \varepsilon = 1$。也就是说，对于完全积性函数 $C$，有 $(A \cdot C) * (B \cdot C) = (A * B) \cdot C$。 --- P1587：推式子然后发现要多次询问 $\sum\limits_{n} \mu(n) [n \perp k]$。然后设 $f(n, k) = \sum\limits_{i = 1}^n \mu(i) [i \perp k] = \sum\limits_{d | k} \mu^2(d) \sum\limits_{i = 1}^{\frac{n}{d}} \mu(i) [i \perp d] = \sum\limits_{d | k} \mu^2(d) f(\frac{n}{d}, d)$。递归计算并记忆化，复杂度 $O(n ^{\frac{2}{3}} +d(k)n ^{\frac{1}{2}})$。 --- BZOJ3512。 ## 1.23 积分 $\displaystyle \int x^n \mathrm{d} x = \dfrac{x^{n + 1}}{n + 1} + C\ (n \neq -1)

\begin{aligned} & \dfrac{(x + \mathrm dx) ^ {n + 1} - x^{n + 1} }{(n + 1) \cdot \mathrm dx} \\ = & \dfrac{\left(\sum\limits_{i = 0}^{n + 1} C_{n + 1}^i x^i (\mathrm dx)^{n - i + 1} \right) - x^{n + 1} }{(n + 1) \cdot \mathrm dx} \\ = & \dfrac{\left(x^{n + 1} + (n + 1) x ^ n \mathrm dx \right) - x^{n + 1} }{(n + 1) \cdot \mathrm dx}\\ = & x^n \end{aligned}

\displaystyle \int x^{-1} \mathrm{d} x = \ln|x| + C

\displaystyle \int \text{杜子德}

后面忘了。

1.23 Powerful Number 筛

对于积性函数 $f$ 构造积性函数 $g$ 使得 $f(p) = g(p)$，那么 $g * h = f$ 中 $h$ 也是积性函数且 $h(p) = 0$，也就是说 $h$ 仅在 PN 处有非 $0$ 值。 $$ \begin{aligned} & \sum_{i = 1}^n f(i) \\ = & \sum_{i = 1}^n (g * h)(i) \\ = & \sum_{i = 1}^n \sum_{d |i} h(d) g\left(\frac{n}{d}\right) \\ = & \sum_{d \in \text{PN}}^n h(d) \sum_{i = 1}^{\frac{n}{d}} g(i) \\ \end{aligned} $$ 所以如果可以快速求或者杜教筛求 $g$ 的前缀和就可以求 $f$ 的前缀和。 $h$ 的值直接求或者递推计算，$ f(p^k) = \sum\limits_{i = 0}^k h(p^i) g(p^{k - i}) \implies g(1) h(p^k) = f(p^k) - \sum\limits_{i = 0}^{k - 1} h(p^i) g(p^{k - i})$。唯一的优势是快，不套杜教筛的情况下复杂度 $O(\sqrt{n} \log n)$。 ## 1.24 Min_25 筛考虑先把质数判掉，剩下的合数都有 $\sqrt{n}$ 以内的质因子，就可以递归计算。对于积性函数 $f$ 构造完全积性函数 $f'$ 使得 $f'(p) = f(p)$。然后先从 $\sum\limits_2^{n} f'$ 里把所有合数以其最小质因数筛出去，那么剩下的 $\sum\limits_{p}^n f' = \sum\limits_{p}^n f$。然后再在 $\sum\limits_{p}^n f$ 里把所有合数以其最小质因数的最大次方筛进去，就得到了 $\sum\limits_{2}^n f$。所以每个合数是从大到小添加质因子得到的。 $$ \begin{aligned} \operatorname{lpf}(n) = & \min\{p \in \mathbb{P} ~\vert~ p | n\} \\ S(n, j) = & \sum_{i = 2}^n f(i) [\operatorname{lpf}(i) > p_j] \\ = & \left( G(n) - \sum_{k = 1}^j f(p_k) \right) + \sum_{k = j + 1}^{p_k^2 \le n} \sum_{e = 1}^{p_k^e \le n} f(p_k^e) \left( S\left(\dfrac{n}{p_k^e}, k\right) + [e > 1] \right) \\ S(n, 0) + f(1) = & \sum_{i = 1}^n f(i) \\ G(n, j) = & \sum_{i = 2}^n f'(i) [i \in \mathbb{P} \lor \operatorname{lpf}(i) > p_j] \\ = & G(n, j - 1) - f'(p_j) \left( G\left(\dfrac{n}{p_j}, j - 1\right) - \sum_{k = 1}^{j - 1} f'(p_k) \right) \\ G(n, 0) = & \sum_{i = 2}^n f'(i) \\ \end{aligned} $$ 巧不巧秒不好说，反正够暴力。$f(p)$ 需要是关于 $p$ 的简单多项式，$f(p^k)$ 要能快速计算。复杂度 $O\left(\dfrac{n ^ {\frac{3}{4}}}{\log n}\right)$ 或 $O(n ^ {1 - \epsilon})$，常数比较小的话能跑 $10^{11}$。 https://www.luogu.com.cn/article/ko7omb31 https://www.cnblogs.com/zbh2047/p/8552551.html https://www.cnblogs.com/GuessYCB/p/10061411.html https://hdmmblz.github.io/2019/07/09/min-25筛x学习笔记与相关题目汇总/ --- 最大质因子：设 $G_1(n)$ 为 $2 \sim n$ 中的质数之和，$S(n, j)$ 为 $2 \sim n$ 中最小质因子大于 $p_j$ 的数的最大质因子之和。 $$ S(n, j) = \left( G_1(n) - \sum\limits_{k = 1}^j p_k \right) + \sum\limits_{k = j + 1}^{p_k^2 \le n} \sum\limits_{e = 1}^{p_k^e \le n} p_k [e > 1] + S\left( \dfrac{n}{p_e^k}, k \right) $$ UOJ188（次大质因子）：设 $G_0(n)$ 为 $2 \sim n$ 中的质数个数，$S(n, j)$ 为 $2 \sim n$ 中最小质因子大于 $p_j$ 的数的次大质因子之和。 $$ S(n, j) = \sum\limits_{k = j + 1}^{p_k^2 \le n} \sum\limits_{e = 1}^{p_k^e \le n} p_k \cdot \left( \left[ \dfrac{n}{p_k^e} \ge p_k \right] \left( G_0\left(\dfrac{n}{p_k^e}\right) - k \right) + [e > 1] \right) + S\left( \dfrac{n}{p_e^k}, k \right) $$ LOJ572：整除分块套杜教筛套 Min_25 或者整除分块套 Min_25 和整除分块。复杂度亚线性，反正能过 $10^9$。最小质因子：设 $S'(n, j)$ 为 $2 \sim n$ 中最小质因子大于 $p_j$ 的数的个数，$S(n, j)$ 为 $2 \sim n$ 中最小质因子大于 $p_j$ 的数的最小质因子之和。 $$ S'(n, j) = \left( G_0(n) - j \right) + \sum\limits_{k = j + 1}^{p_k^2 \le n} \sum\limits_{e = 1}^{p_k^e \le n} [e > 1] + S'\left( \dfrac{n}{p_e^k}, k \right) $$ $$ S(n, 0) = G_1(n) + \sum\limits_{k = j + 1}^{p_k^2 \le n} \sum\limits_{e = 1}^{p_k^e \le n} p_k \cdot \left(S'\left( \dfrac{n}{p_e^k}, k \right) + [e > 1]\right) $$ # Week 27 ## 2.6 点分治静态点分治、点分治序。一般地，树上路径问题的解决方法有枚举端点（换根）、枚举 LCA（DP）、容斥（可差分）和分治（可合并）。分治常用的有链分治（倍增、链剖分）、点分治和边分治。边分治要先转成二叉树以保证复杂度。启发式合并某种意义上也算边分治。 https://liu-cheng-ao.blog.uoj.ac/blog/2969 ## 2.7 $\color{red}{\text{j}}\color{black}{\text{iangly}}$、$\color{black}{\text{j}}\color{red}{\text{qdai0815}}$ 粉丝见面会 ## 2.7 北大招生宣传 ‌清华大学建校的资金主要来源于 1908 年美国退还的部分庚子赔款。‌庚子赔款是 1900 年八国联军侵华后，清廷被迫签订《辛丑条约》赔偿的巨额白银。1904 年，美国表示所得赔款“原属过多”，可用于“退款办学”。经过中美双方多次商谈，最终确定了退款办学的相关事宜，这笔退款主要用于支持清华学堂的建立和发展。‌ ## 2.8 T1 纯推式子，T2 PN 筛板子，T3 期望，T4 Min_25 思想板子。 T3 发现算长度等于某个数的概率不如算长度小于某个数的概率。 # Week 28 ## 2.11 点分治重构树简称点分树，一般用于动态带修的点分治问题。关键在于树上任意一条路径都会在某个重心处被分到两个子树中。单点就从其本身不断往上跳。 ![](https://cdn.luogu.com.cn/upload/image_hosting/zrxp1m9t.png) 路径就找到其 LCA，即把两端点划到两个子树的重心。全局单点就从树根开始往下选择子树递归。全局路径考虑每个 LCA，即重心。 --- byd 你只会找水题就算了，还只放三道是吧。 --- P3241： https://www.luogu.com.cn/article/hmijd1ot --- P3345：口胡做法：从调整答案的方向考虑，发现如果某一子树中的个数大于总数的一半和需要向其方向移动充要，所以可以每次二分找到需要移动到的位置。因为只能处理增加操作，所以再线段树分治，再根号调和，复杂度 $O(q \log^2 n + q \sqrt{n})$，不依赖度数。大概是吧。考虑分治，求答案时从点分树的根往下考虑，如果某个子树的个数大于总数的一半，说明答案在这个子树内。 _非常神奇的是，对于所有数据，这棵树上的点的度数都不超过 20_，所以可以暴力选择子树，计算删掉这条边对答案的影响并向下分治。或者先转二叉树？展现了一种点分治作为分治本身的应用。 --- AT3611：因为不在子图的最小全域木中的边也不在原图的最小全域木中，所以可以把图划分为若干边集，并把每个边集的最小全域木合起来求出最小全域木。然后就可以考虑点分治，每次取经过一个点的所有边求最小全域木。因为 $(u, v)$ 的边权为 $w_u + dep_u + w_v + dep_v$，所以取 $w + dep$ 最小的点向其他点连边即可，复杂度 $O(n \log^2 n)$。还有 Boruvka 的单 $\log$ 做法，但是不会。 --- P2664：用类似 https://www.luogu.com.cn/article/61rei9t8 的做法好像能做到线性，但是现在不会了。考虑点分治。对于分治中心下某子树中某点，如果某颜色在它到分治中心的路径上出现过，那么贡献为其他子树的大小之和；若没有出现，贡献为其他子树中以这种颜色为树根的极大子树大小之和。数颜色一般是困难的（除了莫队），需要设计统计方法使得每种颜色只会被统计一次，所以一般离线，在线就再用可持久化多维护一个时间维度。 ## 2.13 类欧几里德算法用类似欧几里得的方法以取模和交换减小问题规模或转化问题。可以求一次函数下取整（一次函数与坐标轴间整点个数）、一次函数下取整乘系数、一次函数下取整的平方之类的东西。重要的繁衍式子：$n = \sum\limits_{i = 1}^{\infty} [i \le n]$，$n ^ 2 = \left( 2 \sum\limits_{i = 1}^n i \right) - n = \left( 2 \sum\limits_{i = 1}^{\infty} i [i \le n] \right) - n$。 $$ \begin{aligned} & f(a, b, c, n) \\ = & \sum_{i = 0}^n \left\lfloor \frac{ai + b}{c} \right\rfloor \\ = & \sum_{i = 0}^n \left\lfloor \frac{\left(c \left\lfloor \dfrac{a}{c} \right\rfloor + (a \bmod c)\right) i + \left( c \left\lfloor \dfrac{b}{c} \right\rfloor + (b \bmod c) \right)}{c} \right\rfloor \\ = & \dfrac{1}{2} n (n + 1) \left\lfloor \dfrac{a}{c} \right\rfloor + (n + 1) \left\lfloor \dfrac{b}{c} \right\rfloor + f(a \bmod c, b \bmod c, c, n) \\ \\ & f(a, b, c, n) \\ = & \sum_{i = 0}^n \left\lfloor \frac{ai + b}{c} \right\rfloor \\ = & \sum_{i = 0}^n \sum\limits_{j = 1}^{\infty} \left[ j \le \left\lfloor \frac{ai + b}{c} \right\rfloor \right] \\ = & \sum_{i = 0}^n \sum_{j = 1}^{\infty} \left[ j c \le ai + b \right] \\ = & \sum_{i = 0}^n \sum_{j = 0}^{\infty} \left[ (j + 1) c \le ai + b \right] \\ = & \sum_{j = 0}^{\infty} \sum_{i = 0}^n \left[ ai \ge jc + c - b \right] \\ = & \sum_{j = 0}^{\infty} \sum_{i = 0}^n \left[ i \ge \left\lceil \dfrac{jc + c - b}{a} \right\rceil \right] \\ = & \sum_{j = 0}^{\infty} \sum_{i = 0}^n \left[ i \ge \left\lfloor \dfrac{jc + c - b - 1}{a} \right\rfloor + 1 \right] \\ = & \sum_{j = 0}^{\left\lfloor\frac{an + b}{c}\right\rfloor - 1} n - \left\lfloor \dfrac{jc + c - b - 1}{a} \right\rfloor \\ = & n \left\lfloor\frac{an + b}{c}\right\rfloor - f\left( c, c - b - 1, a, \left\lfloor\frac{an + b}{c}\right\rfloor - 1 \right) \\ \\ & f(0, b, c, n) \\ = & (n + 1) \left\lfloor \frac{b}{c} \right\rfloor \\ \\ \\ & g(a, b, c, n) \\ = & \sum_{i = 0}^n i \left\lfloor \frac{ai + b}{c} \right\rfloor \\ = & \frac{1}{6} n (n + 1) (2 n + 1) \left\lfloor \dfrac{a}{c} \right\rfloor + \frac{1}{2} n (n + 1) \left\lfloor \dfrac{b}{c} \right\rfloor + g(a \bmod c, b \bmod c, c, n) \\ = & \frac{1}{2} n (n + 1) \left\lfloor\frac{an + b}{c}\right\rfloor - \frac{1}{2} h(c, c - b - 1, a, \left\lfloor\frac{an + b}{c}\right\rfloor - 1) - \frac{1}{2} f(c, c - b - 1, a, \left\lfloor\frac{an + b}{c}\right\rfloor - 1) \\ \\ & g(0, b, c, n) \\ = & \frac{1}{2} n (n + 1) \left\lfloor\frac{b}{c}\right\rfloor \\ \\ \\ & h(a, b, c, n) \\ = & \sum_{i = 0}^n \left\lfloor \frac{ai + b}{c} \right\rfloor ^ 2 \\ = & \frac{1}{6} n (n + 1) (2 n + 1) \left\lfloor \dfrac{a}{c} \right\rfloor ^ 2 + n (n + 1) \left\lfloor \dfrac{a}{c} \right\rfloor \left\lfloor \dfrac{b}{c} \right\rfloor + (n + 1) \left\lfloor \dfrac{b}{c} \right\rfloor ^ 2 + 2 \left\lfloor \dfrac{b}{c} \right\rfloor f(a \bmod c, b \bmod c, c, n) + 2 \left\lfloor \dfrac{a}{c} \right\rfloor g(a \bmod c, b \bmod c, c, n) + h(a \bmod c, b \bmod c, c, n)\\ = & n \left\lfloor\frac{an + b}{c}\right\rfloor \left( \left\lfloor\frac{an + b}{c}\right\rfloor + 1 \right) - f(a, b, c, n) - 2 f(c, c - b - 1, a, \left\lfloor\frac{an + b}{c}\right\rfloor - 1) - 2 g(c, c - b - 1, a, \left\lfloor\frac{an + b}{c}\right\rfloor - 1)\\ \\ & h(0, b, c, n) \\ = & (n + 1) \left\lfloor\frac{b}{c}\right\rfloor ^ 2 \\ \end{aligned} $$ --- P5179：若 $p$ 和 $q$ 不互质，则必有更优解，所以限制可以忽略。 --- 不难发现类欧就是依托，所以我们有更通用的万能欧几里得算法。几何意义也是依托。 ![](https://cdn.luogu.com.cn/upload/image_hosting/v6yq2fzv.png) 如图 $y = \dfrac{3x + 5}{2}$。折线为其在 $[1, 5]$ 范围内向下取整的值，在 $x$ 到 $x + 1$ 这次向右之前一共向上了 $\left\lfloor \dfrac{3x + 5}{2} \right\rfloor$ 次。设 $y = \dfrac{px + r}{q}$，折线在 $x$ 到 $x + 1$ 这次向右之前一共向上了 $\left\lfloor \dfrac{px + r}{q} \right\rfloor$ 次。 ![](https://cdn.luogu.com.cn/upload/image_hosting/ilygrpss.png) 如图将 $y = \dfrac{3x + 5}{2}$ 向下平移 2 格得到 $y = \dfrac{3x + 1}{2}$，使得截距小于 1。设 $y = \dfrac{px + r}{q}$，将其向下平移 $\left\lfloor \dfrac{r}{q} \right\rfloor$ 格，折线在 $x$ 到 $x + 1$ 这次向右之前一共向上了 $\left\lfloor \dfrac{px + r}{q} \right\rfloor - \left\lfloor \dfrac{r}{q} \right\rfloor = \left\lfloor \dfrac{px + r}{q} \right\rfloor - \dfrac{r - (r \bmod q)}{q} = \left\lfloor \dfrac{px + (r \bmod q)}{q} \right\rfloor$ 次。 ![](https://cdn.luogu.com.cn/upload/image_hosting/gnin5ahj.png) 如图 $y = \dfrac{3x + 1}{2}$ 每次向右之前都有一个向上的方向，将其合并得到 $y = \dfrac{x + 1}{2}$，使得斜率小于 1。设 $y = \dfrac{px + r}{q}$，每次向右之前都有至少 $\left\lfloor \dfrac{p}{q} \right\rfloor$ 次向上，合并后折线在 $x$ 到 $x + 1$ 这次向右之前一共向上了 $\left\lfloor \dfrac{px + r}{q} \right\rfloor - x \left\lfloor \dfrac{p}{q} \right\rfloor = \left\lfloor \dfrac{px + r}{q} \right\rfloor - x \cdot \dfrac{p - (p \bmod q)}{q} = \left\lfloor \dfrac{(p \bmod q) x + r}{q} \right\rfloor$ 次。 ![](https://cdn.luogu.com.cn/upload/image_hosting/ypywydnr.png) 如图 $y = \dfrac{2x + 1}{7}$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/uvnf3oy7.png) 如图将 $y = \dfrac{2x + 1}{7}$ 的横纵坐标翻转使得斜率小于 1 变为斜率大于 1。 ![](https://cdn.luogu.com.cn/upload/image_hosting/xvpqhzm0.png) 再将其平移到从 $(1, 0)$ 开始。翻转前折线在 $y$ 到 $y + 1$ 这次向上之前一共向右了 $\dfrac{p(x - 1) + r}{q} < y + 1 \implies x \le \left\lfloor \dfrac{yq + q - r - 1}{p} + 1 \right\rfloor$，即 $\left\lfloor \dfrac{yq + q - r - 1}{p} \right\rfloor$ 次，再减去开头的 $\left\lfloor \dfrac{q - r - 1}{p} \right\rfloor$ 次，所以翻转之后是 $y = \dfrac{qx + (q - r - 1) \bmod p}{p}$。对于结尾部分，设 $m = \left\lfloor \dfrac{pn + r}{q} \right\rfloor$，则折线定义域为 $[1, m - 1]$，$m - 1$ 到 $m$ 这次向上之前共向右了 $\left\lfloor \dfrac{mq - r - 1}{p} \right\rfloor$ 次，再用 $n$ 减掉把剩下的补到后面即可。边界是 $m = 0$，向右 $n$ 次。虽然要算 $\log$ 次快速幂，但每次的复杂度类似 $\log \dfrac{p}{q} = \log p - \log q$，辗转相除后会相互抵消，总复杂度依然是单 $\log$ 的，只会多一倍常数。应该是吧。 ```cpp node eu(long long p, long long r, long long q, long long n, node U, node R) { if (r >= q) return qpow(U, r / q) * eu(p, r % q, q, n, U, R); if (p >= q) return eu(p % q, r, q, n, U, qpow(U, p / q) * R); long long m = (p * n + r) / q; if (m == 0) return qpow(R, n); return qpow(R, (q - r - 1) / p) * U * eu(q, (q - r - 1) % p, p, m - 1, R, U) * qpow(R, n - (q * m - r - 1) / p); } ``` --- 为什么没有李超套万欧的题。 --- --- --- 字数统计：43241 字符