Luogu

hihocoder

一句话题面：集合 \(S=\{a_i\}\)（\(|S| \leq 3 \times 10^5\)），\(q\) 次询问求是否存在一个子集 \(S_0\subseteq S\)，使得 \(\sum_{a_i\in S_0} a_i = r \pmod M\)（\(M \leq 3\times 10^5​\)）。

题解

具体请参考官方题解。

不得不说实在是很妙…… 在原有 DP 基础上为了加速转移，每次只更新可以更新的部分，跳过不能更新的部分。

每次加入元素 \(a_i\) 时，在一个可能是转移状态的位置之前，DP 数组的前缀是相同的，因此把 DP 数组当成字符串二分 LCP 长度就可以找到这个位置。不能转移的情况是，更新之前这一位就是 \(1\)，也就是没加入 \(a_i\) 时就可以取到了。

判断 LCP 用 Hash 即可，树状数组维护。这里学习到一个小技巧：普通 Hash 的 MOD 最好选择它的一个原根作做幂。记得提前算好原根的 \(n\) 次幂和对应的逆，不然就会像我一样疯狂 TLE。

复杂度证明十分地巧妙，通过等价代换分析出了总更新次数。另外，这套题的 B 题用了排序不等式证明复杂度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

#include<cstdio>
#include<vector>
using namespace std;

const int N=300000+5,MOD=998244353,G=3;

typedef long long ll;
int f[N];

struct BITree{
    ll t[N];
    int Lowbit(int x){
        return x&-x;
    }
    void Add(int p,ll v){
        for(;p<N;p+=Lowbit(p))
            t[p]=(t[p]+v)%MOD;
    }
    ll Query(int p){
        ll ret=0;
        for(;p;p-=Lowbit(p))
            ret=(ret+t[p])%MOD;
        return ret;
    }
};

inline ll QPow(ll bas,ll t){
    ll ret=1;bas%=MOD;
    for(;t;t>>=1,bas=bas*bas%MOD)
        if(t&1LL)ret=ret*bas%MOD;
    return ret;
}

inline ll Inv(ll x){
    return QPow(x,MOD-2);
}

BITree t;
ll pow3[N],inv3[N];

void InitHash(){
    pow3[0]=1;
    for(int i=1;i<N;i++)
        pow3[i]=pow3[i-1]*G%MOD;
    for(int i=0;i<N;i++)
        inv3[i]=Inv(pow3[i]);
}

ll Hash(int l,int r){
    ll ret=(t.Query(r)-t.Query(l-1))%MOD;
    ret=ret*inv3[l-1]%MOD;
    return (ret+MOD)%MOD;
}

int n,m;
ll det;

inline bool Check(int st1,int st2,int M){
    ll h1=(Hash(st1,st1+M-1)+det)%MOD;
    ll h2=Hash(st2,st2+M-1);
    return h1==h2;
}

int BSearch(int L,int R,int st1,int st2){
    while(L<R){
        int M=(L+R)/2;
        if(Check(st1,st2,M))L=M+1;
        else R=M;
    }
    return L;
}

int q[N];

int main(){
    InitHash();
    scanf("%d%d",&n,&m);

    f[1]=1;
    t.Add(1,pow3[1]);

    for(int i=1,a,len;i<=n;i++){
        scanf("%d",&a);
        q[0]=0;		//q: update

        det=0;len=1;
        while(Check(1,1+a,m-a)==0){
            len=BSearch(len,m-a,1,1+a);
            if(f[len]==0&&f[a+len]==1)
                det=(det+pow3[len])%MOD;
            else{
                det=(det+MOD-pow3[len])%MOD;
                q[++q[0]]=a+len;
            }
        }

        det=0;len=1;
        while(Check(m-a+1,1,a)==0){
            len=BSearch(len,a,m-a+1,1);
            if(f[m-a+len]==0&&f[len]==1)
                det=(det+pow3[len])%MOD;
            else{
                det=(det+MOD-pow3[len])%MOD;
                q[++q[0]]=len;
            }
        }

        for(int j=1;j<=q[0];j++){
            t.Add(q[j],pow3[q[j]]);
            f[q[j]]=1;
        }
    }

    int nQ;
    scanf("%d",&nQ);
    while(nQ--){
        int r;
        scanf("%d",&r);
        printf(f[r+1]?"YES\n":"NO\n");
    }

    return 0;
}

这是一个测试博客格式与渲染的页面。

一些配置 hexo 和 nexT 时参考的文章。

2-SAT（2-satisfiability）即给定一些布尔变量的或关系，判断是否有满足所有关系的变量取值。SAT 问题是 NPC 问题，2-SAT 问题是 P 问题。

主要说明优化 DP 的一些方法。

四边形不等式

四边形不等式是一个神奇的二元函数的结论，利用它可以得到决策的单调性，从而加速寻找转移状态的时间。然而我对这个东西并没有研究，因此也只能谈一下结论。

对函数 \(w_{i,j}\)，若满足

\[w_{i,j}+w_{i',j'}\leq w_{i,j'}+w_{i',j} \quad (i\leq i'\leq j\leq j')\]

则函数 \(w_{i,j}\) 满足四边形不等式。令 \(s_{i,j}\) 表示 \(w_{i,j}\) 得到最优值的转移来源，则有：

\[s_{i,j}\leq s_{i,j+1}\leq s_{i+1,j+1} \quad (i\leq j)\]

即决策具有单调性。利用这个性质可以缩小决策集合，加速决策时间。但是不等式仅仅缩小了范围，并不意味着当一个决策比之前的决策和后一个决策更优时，就不继续考察后面的决策。

（其实还有一个区间包含单调不等式，但是我没看出来有什么用）

斜率优化

斜率优化是优化一类动态规划的方法，通常的实现是维护一个凸包从而达到 \(\mathcal{O}(\log {n})\) 甚至 \(\mathcal{O}(1)\) 的转移时间复杂度。维护凸包通常采用单调队列或平衡树。

一般情况

从典型的情况着手。假设我们有一个转移方程：

\[f_i = \min\{-a_i*b_j+c_j\}+d_i \quad (0\leq j<i)\]

很明显，这个方程在朴素的情况下需要对每个 \(i\) 枚举 \(j\)，时间复杂度是 \(\mathcal{O}(n^2)\) 的。但是我们发现这个方程与 \(i\) 和 \(j\) 有关的项只有一项，而其他项要么只与 \(i\) 有关，要么只与 \(j\) 有关。令 \(x=b_j,y=c_j,d_i=t\)，则对确定的 \(j\)，\(x\) 与 \(y\) 都是确定的。假设此时 \(j\) 为最优转移。代入有：

\[ \begin{aligned} f_i&=-a_i*x+y+t \\ \Rightarrow y&=a_i*x+f_i-t \end{aligned} \]

由于 \(t\) 只与 \(i\) 相关，因此我们可以认为 \(y = a_i x+f_i\)。此时我们相当于在满足 \(0\leq j<i\) 的 \(j\) 所代表的点集中，找到使得斜率 \(k=a_i\) 的直线在 \(y\) 轴上的截距最小的点。不难看出这个点只能在点集的下凸包上，否则其他点都没有该点优。因此我们需要维护一个下凸的点集（相邻边斜率递增）。

排除不必要点

考虑在候选点集里，哪些点是不必要的。方便考虑，我们先假设 \(a_i\) 非降，\(b_j\) 严格递增，则插入点是按横坐标顺序排列的。由于斜率非降，我们通过画图可以知道若点 \(j\) 最优化了 \(i\)，则对 \(\forall i'>i\)，其最优转移都不可能在 \(j\) 之前的点 \(k\) 取到（斜率非降 \(\Leftrightarrow\) 极角非降，考虑旋转卡壳的过程对蹱点的单调转移），因此转移单调，可以删除 \(j\) 前面的点。

再考虑插入新点 \(i\) 的情况。如果当前加入了 \(i\) 会使得下凸性质被破坏，则当前点集最后一个点必定在下凸的上方，也就不会再被选中，直接删除。这个判断如果直接比较斜率容易出现精度误差甚至斜率不存在，我更喜欢用叉积计算。

这样，我们相当于在点集开头与结尾维护了下凸性质，并动态删除多余的点。这个数据结构可以采用双端队列，队首就是最佳转移。每个点最多入队出队一次，均摊时间复杂度为 \(\mathcal{O}(1)\)。同理，如果函数转移最大值，则需要维护上凸性质。具体维护什么还要由点集的给出顺序（即 \(x_i\) 的趋势，如逆序给出需要逆序维护凸包）而定。

更一般的情况

我们以上维护凸包的讨论是建立在 \(a_i\)（斜率）非降，\(b_j\)（横坐标）严格递增的情形上。假如不满足呢？

斜率无序

斜率无序，则决策单调性不满足，我们需要二分找到凸包上的切点。不难看出目标函数的斜率在最佳转移两侧的斜率之间。查找的时间复杂度为 \(\mathcal{O}(\log n)\)。

横坐标无序

横坐标无序，则不能直接在队尾插入，需要一个能动态维护序列的数据结构 —— 平衡树。查找到要插入的位置后，维护插入点左右的凸包性质。需要特判点在凸包内的情况，这样的点不会更新凸包。如果使用了叉积，就不需要考虑重点或重横坐标的情况。

当然如果斜率和横坐标都无序，那就只能考虑平衡树上的凸包维护。注意细节。

练习

斜率优化的题目我没做很多，不过感觉都是套路（除了诗人小 G）。

基础

HDU3507 打印文章

令 \(sumC _i = \sum _{j=1}^i c_j\)，则有：

\[ \begin{aligned} f_i&= \min / \max\{f_j+(sumC_i-sumC_j + M)^2\} \\ &= \min / \max\{-2*sumC_i*sumC_j-2*sumC_j*M+f_j+sumC_j^2\} + (sumC_i+M)^2\\ \end{aligned} \]

同时维护两个凸包。

HNOI2008 玩具装箱

令 \(sumC _i = \sum _{j=1}^i c_j\)，则有

\[f_i = \min\{f_j+(i-j-1+sumC_i-sumC_j - L)^2\}\]

发现 \(i\) 有两个变化量 \(i\) 与 \(sumC_i\)，不好处理。但是我们能够合并。重新定义 \(sumC_i=sumC_i+i\)，则：

\[f_i = \min \{f_j+(sumC_i-sumC_j -L-1)^2\}\]

展开式子维护下凸包。

ZJOI2007 仓库建设

维护下凸包。题目应该有特判：只要最后的工厂是空的，就不用都运到最后一个工厂，这样费用反而会变小。不过数据没有这种坑点，因此直接输出 \(f_n\) 也没问题。

CEOI2004 锯木厂选址

不用随机算法就水水的。枚举第二个厂 \(i\) 与第一个厂 \(j\)，化好式子之后发现 \(x\) 是递增的，斜率是非降的，直接队列就可以，不需要平衡树。

进阶

SDOI2012 任务安排

这个题明显有后效性，每次分配一段工作就对后面的完成时间增加 \(S\)。我们发现对确定的分段 \(i\)，其对后面的影响（假设对自己的影响已经计算了）是确定的值 \(S*\sum_{j=i+1}^n\)，因此如果我们提前计算影响，就可以消除后效性。

令 \(sumT_i=\sum_{j=1}^i T_j,sumF_i=\sum_{j=1}^i F_j\)，则：

\[f_i = \min\{f_j+[sumT_i+S*(sumF_n-sumF_j)]*(sumF_i-sumF_j)\}\]

明显展开后 \(x = sumF_j,k_i=sumT_i\)，然而坑点是有 \(t\leq0\) 的数据，\(sumT_i\) 不一定递增。需要二分寻找最优转移。

BSOJ1517 斜率优化

题意：给定 \(a,b\) 数组与 \(f_i= \begin{cases} 0, &i=0 \\ \min\{f_j-a_i*b_j\}, &0\leq j<i\leq n \end{cases}\)，\(minimize\ f_n\)。

坐标和斜率都不单调，上平衡树维护。可以用 Splay，我用的是非旋转式 Treap。比较惊讶于我的寻找是 Split+Merge+BSearch，总时间复杂度为 \(\mathcal{O}(n\log ^2n)\)，竟然也跑得过 \(n\leq 200000\)，感觉奥妙重重。

高级

没做过高级的。至少还没做完货币交换。

NOI2009 诗人小 G

明显跟内容无关，我们只需要每一行的长度 \(len_i\)。令 \(sumLen_i=\sum_{j=1}^i len_j\)，再令 \(sumLen_i=sumLen_i+i\)，则有：

\[ f_i = \min\{f_j+|(sumLen_i-sumLenj-1-L)^p|\} \]

对于 \(p=2\) 的点就是基础的斜率优化，可以过两个数据点。然而 \(p\leq 10\)，没办法斜率优化。打个表发现决策具有单调性，然后我们也可以（通过复杂的）证明得到这个式子满足四边形不等式 \(\Leftrightarrow\) 决策具有单调性，就可以维护啦。

具体来说，我们插入时考虑决策 \(i\) 可能是哪些状态的最优决策，用 \(a_i\) 表示 \(i\) 的最优决策的最大值，则不难看出 \(a_i\) 是非降的。因为决策单调，决策 \(j\) 如果是 \(i\) 的最优决策，则 \(i\) 后面的所有状态的可能最优决策都更新为 \(j\)。我们可以用栈维护每个决策能更新的状态的起始点，一个决策一旦被覆盖就不可能再出现。步骤如下：

1. 对栈顶元素 \(top\) 的起始点 \(pos_{top}\) 考察用当前决策 \(i\) 是否会更优，是则出栈，否则重复。
2. 此时决策 \(i\) 的起始点一定在 \((pos_{top},n]\) 之间，二分查找 \(pos_i\)。

每次寻找最优决策时间二分 \(\mathcal{O}(\log n)\)（如果维护队列为 \(\mathcal{O}(1)\)），维护栈时每个元素最多出栈入栈一次，平摊 \(\mathcal{O}(1)\)，二分 \(\mathcal{O}(\log n)\)。所以单次数据复杂度为 \(\mathcal{O}(n\log n)\)，完美解决。

不过严格来说，这跟斜率优化没有太大关系，重点在转移单调。

总结

斜率优化维护一个凸包从而达到 \(\mathcal{O}(\log n)\) 甚至 \(\mathcal{O}(1)\) 的转移复杂度，从而加速转移。一般需要转移具有单调性，可以通过四边形不等式证明。具体有几个要点：

• 转移表达式只与当前状态 \(i\) 与候选状态 \(j\) 有关，而不与其他变量 \(k\) 有关；或与 \(k\) 有关，但在 \(k\) 确定时 \(i\) 只与 \(j\) 有关。这样确保了二维平面上每个候选状态点 \(j\) 的存在。

• 斜率优化中，表达式的 \(x\) 值为与 \(i\) 相关的 \(j\) 的变量，\(y\) 值为只与 \(y\) 相关的变量。

• 斜率无序：二分；横坐标无序：平衡树

• 四边形不等式：\(w_{i,j}+w_{i',j'}\leq w_{i,j'}+w_{i',j} \quad (i\leq i'\leq j\leq j')\) 满足四边形不等式的式子具有转移单调性，可以采用栈维护转移集合。要确定一个式子满足决策单调，除了证明通常采用打表观察（不一定正确）。

• 有后效性的转移可以提前计算影响。

矩阵是个很神奇的东西，可惜我涉猎较少，只能浅谈矩阵的应用。

莫比乌斯反演是偏序集上的一个反演，不过在此处我们只讨论整数格上的莫比乌斯反演。

莫比乌斯反演

整数格上的莫比乌斯反演

定义 \(\mu\) 函数：

\[ \mu(n)= \begin{cases} 1,&n=1 \\ (-1)^m,&n=\prod_{i=1}^m p_i^{k_i},\prod_{i=1}^m k_i=1 \\ 0,&otherwise\\ \end{cases} \]

函数有两个性质。

• \(\mu\) 是积性函数。
• \(\sum_{i=1}^n\mu(i)= \begin{cases} 1,&n=1 \\ 0,&othewise\\ \end{cases}\)

第一条性质说明 \(\mu\) 可以线性筛；第二条性质提供了我们一个当且仅当 \(n=1\) 时计数的函数，因此在遇到求 \((i,j)=1\) 的问题中通常会用到它。

直接给出代码。

1
2
3
4
5
6
7
8
9
10
11

void Init(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!notPri[i])pri[siz++]=i,mu[i]=-1;
        for(int j=0;j<siz&&i*pri[j]<N;j++){
            int nxt=i*pri[j];notPri[nxt]=1;
            if(i%pri[j])mu[nxt]=-mu[i];
            else {mu[nxt]=0;break;}
        }
    }
}

当出现平方因子就退出筛法保证了每个数只会被最小的因子筛去，因此时间复杂度线性。\(\mu_i=0\) 的情况是由最小因子筛掉的，而其他情况都是由 \(\mu_i=-\mu_j\) 得到的。

反演

想学习很多反演，但是太菜了只会这个.jpg

以后可能会补吧。

若函数 \(f(n),g(n)\) 为数论函数，且满足 \(f(n)=\sum_{i|n}g(i)\)，则有：

\[g(n)=\sum_{i|n}f(n)\mu\left(\frac ni\right)=\sum_{i|n}f\left(\frac ni\right)\mu(i)\]

若函数 \(f(n),g(n)\) 为数论函数，且满足 \(f(i)=\sum_{d=1}^{\left\lfloor n/i \right\rfloor}g(i*d)\)，则有：

\[g(i)=\sum_{d=1}^{\left\lfloor n/i \right\rfloor}f(i\times d)\mu(d)\]

证明略去。事实上两种方法都可以比较方便地运用，一般第一种不需要构造函数，而第二种需要构造函数。

常用反演

定义符号

\[[exp]= \begin{cases} 1,&exp=true\\ 0,&exp=false \\ \end{cases} \]

定义函数 \(e(n)=[n==1],id(n)=n\)，则有：

\[ e=\mu \times 1 \\ id=\phi \times 1 \]

乘法代表 Dirichlet 卷积。因此反演也可以表示为：

\[f=g \times 1 \Leftrightarrow g=f \times \mu\]

应用

二维 GCD 计数前缀和

求 \(\sum_{i=1}^n \sum_{j=1}^m [(i,j)==k]\) 且 \(n\leq m\)。

不使用函数变换的方法

不难发现：

\[ \begin {aligned} \sum_{i=1}^n \sum_{j=1}^m [(i,j)==k] =&\sum_{i=1}^n \sum_{j=1}^m \left [\left (\frac ik,\frac jk\right)==1\right] \\ =&\sum_{i=1}^n \sum_{j=1}^m e\left (\left (\frac ik,\frac jk\right)\right) \\ =&\sum_{i=1}^n \sum_{j=1}^m \sum_{g|(i,j)} \mu (g) \\ =&\sum_{i=1}^n \sum_{j=1}^m \sum_{g|i\text {且} g|j} \mu (g) \\ =& \sum_{g=1}^n\sum_{i=1}^{\left\lfloor n/g\right\rfloor} \sum_{j=1}^{\left\lfloor m/g\right\rfloor} \mu (g) \\ =& \sum_{g=1}^n \mu (g) \sum_{i=1}^{\left\lfloor n/g \right\rfloor} \sum_{j=1}^{\left\lfloor m/g\right\rfloor} \\ \end {aligned} \]

而 \(\left\lfloor \dfrac ng\right\rfloor\) 只有不超过 \(\sqrt{n}\) 种取值，\(\left\lfloor \dfrac ng\right\rfloor\) 和 \(\left\lfloor \dfrac mg\right\rfloor\) 只有不超过 \(\sqrt{n}+\sqrt{m}\) 种取值，因此可以将 \([1,n]\) 分成 \(\sqrt{n}+\sqrt{m}\) 块，每一块的 \(\left\lfloor \dfrac ng\right\rfloor\) 和 \(\left\lfloor \dfrac mg\right\rfloor\) 取值都不变，则我们预处理 \(\mu\) 后可以对一块区间进行 \(\mathrm{O}(1)\) 的统计，总时间复杂度为 \(\mathrm{O}(\sqrt{n}+\sqrt{m})\)。

使用函数变换的方法

令 \(f(k)=\sum_{i=1}^n \sum_{j=1}^m [(i,j)==k]\)，\(g(k)=\sum_{i=1}^n \sum_{j=1}^m [k|(i,j)]\)，则 \(f(k)\) 就是我们要求的答案。很明显 \(k|(i,j) \Leftrightarrow k|i\text {且} k|j\)，因此 \(g(k)=\left\lfloor \dfrac nk \right\rfloor \left\lfloor \dfrac mk \right\rfloor\)。

发现 \(g(k)=\sum_{d=1}^{\left\lfloor n/k \right\rfloor}f(d \times k)\)，因此有：

\[ \begin{aligned} f(k)=&\sum_{d=1}^{\left\lfloor n/k \right\rfloor}g(d \times k)\mu(d) \\ =&\sum_{d=1}^{\left\lfloor n/k \right\rfloor}\left\lfloor \dfrac n{dk} \right\rfloor \left\lfloor \dfrac m{dk} \right\rfloor\mu(d) \end{aligned} \]

令 \(n'=\left\lfloor \dfrac nk \right\rfloor,m'=\left\lfloor \dfrac mk \right\rfloor\)，则

\[ \begin{aligned} f(k)=&\sum_{d=1}^{\left\lfloor n/k \right\rfloor}\left\lfloor \dfrac {n'}d \right\rfloor \left\lfloor \dfrac {m'}d \right\rfloor\mu(d) \end{aligned} \]

类似上面可以证明 \(n',m'\) 的取值个数，因此求解也是 \(\mathrm{O}(\sqrt{n}+\sqrt{m})\) 的。

好了，那求了一个区间后，怎么寻找下一个区间？假设我们当前区间开头为 \(i\)，并假设下一个区间为 \(j\)，则：

\[ \begin{aligned} \left\lfloor \dfrac {n'}i \right\rfloor &\leq \left\lfloor \dfrac {n'}j \right\rfloor \\ \Rightarrow \left\lfloor \dfrac {n'}i \right\rfloor &\leq \dfrac {n'}j \\ \Rightarrow j &\leq \dfrac {n'}{\left\lfloor {n'}/i \right\rfloor} \\ \Rightarrow j &\leq \left\lfloor \dfrac {n'}{\left\lfloor {n'}/i \right\rfloor}\right\rfloor\\ \end{aligned} \]

同理可得 \(m\)。因此 \(j=\min\left( \left\lfloor \dfrac {n'}{\left\lfloor {n'}/i \right\rfloor} \right\rfloor,\left\lfloor \dfrac {m'}{\left\lfloor {m'}/i \right\rfloor} \right\rfloor\right)\)。这个技巧在很多莫比乌斯反演的题目都用得上。

求约数个数和

直接给出结论：

若 \(d(n)\) 为 \(n\) 的约数个数，则有：

\[ d(nm)=\sum_{i|n} \sum_{j|m} [(i,j)==1] \]

证明不略。假设 \(nm=\prod_{i=1}p_i^{x_i},n=\prod_{i=1}p_i^{y_i}\)，则 \(m=\prod_{i=1}p_i^{x_i-y_i}\)。

对于 \((i,j)=1\)，考虑因子 \(p_k\)，则 \(i\) 和 \(j\) 的 \(p_k\) 项指数不能都不为 \(0\)。当 \(i\) 的 \(p_k\) 为 \(0\) 时，\(j\) 有 \(x_k-y_k+1\) 种取值；当 \(j\) 的 \(p_k\) 为 \(0\) 时，\(i\) 有 \(y_k+1\) 种取值；\(i,j\) 的 \(p_k\) 项可以都取 \(0\)。因此 \(i\) 与 \(j\) 的 \(p_k\) 项有 \(x_k+1\) 种二元组 \((i,j)\) 的取值，总二元组方案数为 \(\prod_{i=1} x_i+1\)，满足约数个数公式。

然后还有个推广的神奇大结论：

\[\sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left\lfloor \dfrac{y_i}{x_i} \right\rfloor \prod_{i < j } [(x_i, x_j)=1]\]

太神奇，证明需要二重数学归纳，略过。

杜教筛

高端，不会。

min-25 筛

高端，不会。

练习

莫比乌斯的题目通常能转化为 \((i,j)=1\) 的计数问题，而转化为计数问题我们就容易通过分块求解了。

基础

POI2007 Zap

二维 GCD 计数前缀和。

HAOI2011 Problem b

POI2007 Zap 的加强版，容斥原理加加减减就好了。

BZOJ2820 YY 的 GCD

仍然是二维 GCD 计数前缀和，不过需要 \((i,j)\) 为质数。只要预处理质数的 \(\mu\) 前缀和就好了。

SDOI2008 仪仗队

不被挡住即行列 \((i,j)=1\)（从 \(0\) 标号），因此答案为 \((\sum_{i=1}^n \sum_{i=1}^n [(i,j)==1])+2\)（\(2\) 个是 \((0,1),(1,0)\)）。最终化为 \((\sum_{g=1}^n \mu(g)\left\lfloor \dfrac ng\right\rfloor ^2)+2\)，分块求解。

进阶

SDOI2015 约数个数和

是道好题，然而需要结论。

令 \(n'=\dfrac ng,m'=\dfrac mg\)，则

\[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^m d(ij) =&\sum_{i=1}^n \sum_{j=1}^m [(i,j)==1] \\ =&\sum_{i=1}^n \sum_{j=1}^m {\left\lfloor \dfrac ni\right\rfloor}{\left\lfloor \dfrac mj\right\rfloor} \sum_{g|(i,j)}\mu(g) \\ =&\sum_{g=1}^n\mu(g)\sum_{i=1}^{\left\lfloor n/g\right\rfloor} \sum_{j=1}^{\left\lfloor m/g\right\rfloor} \dfrac n{ig} \dfrac m{jg} \\ =&\sum_{g=1}^n\mu(g)\sum_{i=1}^{n'} \sum_{j=1}^{m'} \dfrac {n'}i \dfrac{m'}j \\ =&\sum_{g=1}^n\mu(g)\sum_{i=1}^{n'} \dfrac {n'}i\sum_{j=1}^{m'} \dfrac{m'}j \\ \end{aligned} \]

然后就可以预处理 \(f(n)=\sum_{i=1}^n \dfrac ni​\) 的值，每次询问就可以分块解决。之所以要预处理 \(f(n)​\)，是因为在倒数第二步时如果采用直接计算 \(\sum_{i=1}^{n'} \sum_{j=1}^{m'} \dfrac {n'}i \dfrac{m'}j​\) 开销是很大的。但如果我们能预处理，就能做到 \(\mathrm{O}(1)​\) 计算。

预处理时间复杂度 \(\mathrm{O}(n\sqrt{n})\)，单次询问时间复杂度 \(\mathrm{O}(\sqrt{n})\)。

HNMTC2015#5 Lucas 的数论

发现是 SDOI2015 约数个数和的单询问加强版本，上面对 \(\mu\) 前缀和的 \(\mathrm{O}(n)\) 时间复杂度已经不能满足我们了。

式子最终可以推成这样：

\[\sum_{g=1}^n\mu(g) d(n')^2 \]

单次 \(f(n')\) 可以分块求。假设我们预处理好了 μ 的前缀和，时间复杂度就是 \(\mathrm{O}(\sqrt{n})\) 的。这里就有个求 \(μ\) 的前缀和 \(sum\) 的奇技淫巧了：

\[sum(n)=1-\sum_{i=2}^n sum(\left\lfloor \dfrac ni \right\rfloor)\]

递归求解。注意这也是能分块的，因此一层的时间为 \(\mathrm{O}(\sqrt{n})\)，据说没有记忆化搜索时计算一次的时间复杂度为 \(\mathrm{O}(n^{\frac 23})\)。不过事实上我们可以记忆化搜索，或者线筛预处理出 \(n\leq 5000000\)（测试得到这个效率比较高）的 \(\mu\) 前缀和减少计算。

总时间复杂度未知，不过测试极限数据还是挺极限的。

高级

没做过什么高级的。

总结

莫比乌斯反演基本上离不开 GCD 和两个累和符号，而且重点往往是把式子化成统计 GCD=1 个数的形式，并反演求解。求解一般通过分块和预处理 \(\mu\) 前缀和的方式 \(\mathrm{O}(\sqrt{n})\) 求和。

• \(e=\mu \times 1,id=\phi \times 1\)

• \(\mu\) 函数的性质：

  • \(\mu\) 是积性函数。
  • $_{i=1}^n(i)= \[\begin{cases} 1,&n=1 \\ 0,&othewise\\ \end{cases}\] $

• \(\mu\) 的神奇前缀和计算：\(sum(n)=1-\sum_{i=2}^n sum(\left\lfloor \frac ni \right\rfloor)\)

• 当待分块函数（如 \(\mu\)）可以单独提出预处理时，可以通过此降低时间复杂度。

• 若多次询问中，分块区域下含有 GCD 的枚举值 \(g\) 和 \(i\) 或 \(j\) 之一，可以通过枚举 \(ig\) 或 \(jg\)，再枚举 \(g\) 加速。（说法很意识流，详见莫比乌斯反演简要笔记 - GCD 的幂）

• 积性函数有时不好证明，可以打表观察。重点观察幂和质数的值。

网络流，就是一张有向图中给每一边分配一个容量，流可以沿着有容量的边移动。对一个给定的网络，其一个可行流为从源点到汇点的一种流量方案。

网络流问题就是解决最大流、可行流、费用流等抽象问题的一种模型。对一个可行流来说，它有如下特性：

• 除了源汇点外，每一个点的入流与出流相等
• 经过每条边的流量不超过该边容量上限

则最大流就是到达汇点的流量最多的一个可行流，它也满足上述性质。

## 最大流

求最大流可以采用 Dinic、SAP、ISAP 等算法，但我们主要介绍 Dinic。Dinic 算法分为寻找分层图与增广两个部分。下面不加解释地放上 Dinic 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

struct Dinic{
    struct Edge{int v,res;};
    vector<Edge> edg;
    vector<int> a[V];
    int st,ed;

    void AddEdge(int u,int v,int cap){
        edg.push_back((Edge){v,cap});
        edg.push_back((Edge){u,0});
        int siz=edg.size();
        a[u].push_back(siz-2);
        a[v].push_back(siz-1);
    }

    int dep[V];
    bool BFS(){
        memset(dep,-1,sizeof(dep));
        queue<int> q;
        q.push(st);dep[st]=0;

        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<a[u].size();i++){
                Edge e=edg[a[u][i]];
                if(dep[e.v]==-1&&e.res>0)
                    q.push(e.v),dep[e.v]=dep[u]+1;
            }
        }

        return dep[ed]!=-1;
    }

    int cur[V];
    int DFS(int u,int minF){
        if(u==ed||minF==0)return minF;

        int tmpF,sumF=0;
        for(int &i=cur[u];i<a[u].size();i++){
            Edge &e=edg[a[u][i]];
            if(dep[e.v]==dep[u]+1&&(tmpF=DFS(e.v,min(minF,e.res)))>0){
                e.res-=tmpF,edg[a[u][i]^1].res+=tmpF;
                sumF+=tmpF;minF-=tmpF;
            }
            if(minF==0)break;
        }

        return sumF;
    }

    int MaxFlow(){
        int ret=0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            ret+=DFS(st,INF);
        }
        return ret;
    }
};

上述代码用残量表示边的流量数据。对这份代码的解释很容易在网络上找到，在此不做赘述，而只点出实际写时的易错点：

• 寻找分层图时，不能经过残量为 0 的边。
• 利用当前弧结构保存时，每一次寻找增广路前要清零。并且寻找增广路时要使用引用来更新当前弧。
• 寻找增广路时要对当前边进行修改，因此要对边使用引用而不能单纯复制内容
• 对边的四个操作要保证修改的对象和数值是否正确
• 如果流量为 double 类型，需要 DCmp 判断是否为 0，而不能直接与 0 比较

这是一些很 naive 且很容易忘记的错误。放出以警示自己。

### 带上下界的流

带上界的流一般都采用拆点的方式建图来保证其上下界功能。考虑好必须经过的流量是哪些，可以经过的流量是哪些。

#### 带上下界可行流

##### 无源汇

对于 $E = (u , v) \(，若其流量限定为 \) [low , upp]$，则我们可以先考虑特殊情况。

• 没有下界：普通的网络流，从 \(u\) 向 \(v\) 连容量为 \(upp\) 的边。
• 没有上界：\(u\) 节点必须输出 \(low\) 流量，\(v\) 节点必须流入 \(low\) 流量。根据这个条件，可以考虑从 \(u\) 向 \(t\) 连流量为 \(low\) 的边，从 \(s\) 向 \(v\) 连流量为 \(low\) 的边，这样就满足了上述条件。

我们发现这两个不互相干扰，一起使用即可。明显，整个网络拥有一个可行流的等价条件是，新增的下界边都满流，否则没有可行流。

由于新网络入流与出流相等，而无源汇的网络满足流量平衡，因此 s 的出流等于 t 的入流，也就满足了新增加的边如果从 \(s\) 得到了流量，则一定跑到了 \(t\)，而不会中途消失。此时 t 的最大流就是经过这些下界边的总流量。

##### 有源汇

从 \(t\) 向 \(s\) 连一条容量为 \(\infty\) 的边，这样网络就变成无源汇的上下界，跑可行流即可。之所以需要变成无源汇而不能拆边后直接跑，是因为无源汇的网络做法考虑了流量平衡，而有源汇的网络明显源汇是不平衡的。如果不连 $(t , s) \(的边，那么改建后原网络的 \)s$ 根本就没有流量。这很明显不可行。

#### 有源汇带上下界最大流

##### 普通做法

我们的立足点是无源汇上下界可行流的求法，因此考虑把有源汇先转成无源汇。按照无源汇可行流的方法建图并跑最大流，得到的是一个原图的可行流，此时的下界应该是填满的（显然，不填满就连可行流都没有）。在残余网络上从原图的 \(S\) 到 \(T\) 跑最大流就是答案。（当然我不是很理解。）

##### 二分做法

我们仍转换为无源汇，但是设从 \(T\) 到 \(S\) 的边有下界 \(x\)，并跑无源汇可行流。明显，如果新图具有可行流，则说明原图能有 \(x\) 的流量从 \(S\) 到达 \(T\)，否则没有。这个性质可以二分。

#### 带上下界最小流

如果不带上下界，则最小流就是零流，没有什么好求的。

##### 普通做法

考虑转化为无源汇，但这次我们不连接从 \(T\) 到 \(S\) 的边，直接跑 \(SuperS\) 到 \(SuperT\) 的最大流。再加上从 \(S\) 到 \(T\) 的边，从 \(SuperS\) 到 \(SuperT\) 跑一次最大流。若从 \(S'\) 出发的边满流，则 \(( T , S )\) 的流量为最小流，反之无解。（当然我不是很理解。）

##### 二分做法

我们仍转换为无源汇，但是设从 \(T\) 到 \(S\) 的边有下界 \(x\)，并跑无源汇可行流。明显，如果新图具有可行流，则说明原图能有 \(x\) 的流量从 \(S\) 到达 \(T\)，否则没有。这个性质可以二分。

#### 总结

我们所有上下界流的基础都是建立在上下界无源汇可行流上，因此这个模型的转换是很重要的。另外，上下界最大 / 最小流的二分解法虽然比普通解法多出一个 \(\log\)，但是却很容易理解。实际运用上应该是足够的。

## 最小割

流网络 $ G = (V , E) \(的割（Cut）\) [ S , T ] \(将点集 \) V \(划分为 \) S \(和 \) T ( T = V − S )\(两个部分，使得源 \) s ∈ S \(且汇 \)t ∈ T \(。符号 \) [ S , T ] \(代表一个边集合 \) { u , v | u , v ∈ E , u ∈ S , v ∈ T } \(。割 \) [ S , T ] \(的容量（Capacity）定义为 \) c ( S , T ) \(，一般记为 \) c [S , T] $。一个网络的最小割也就是该网络中容量最小的割。（定义来自《最小割模型在信息学竞赛中的应用》 胡伯涛）

注意边集中方向为 \(T\to S\) 的边的容量不计算在割集内。即最小割的容量只为顺着 \(S\to T\) 到达的边的容量和。

最小割拥有一些不错的性质：

• 最小割将点集分割成两个部分，且最小割只包含了两端点属于不同点集的边的容量
• 最大流最小割定理：一个网络中的最大流等于最小割

第二个性质很重要，它给了我们一个求最小割的方法。而第一个性质给了我们一个转换模型的思路。我们给出如下性质：

• 最小割一定是最大流中的满流边，但满流边不一定是最小割中的边

这个性质的反例可以在论文中找到。因此寻找最小割边时，需要从源点 DFS 顺着有残量的边遍历，则两端点只被遍历一个的边为最小割边。注意这个有残量的边包括网络中的反边，有些点可能能从反边被到达，因此需要 DFS 而不能单独认为满流边就是最小割边。

### 平面图最小割

可以参考论文《两极相通 —— 浅析最大 — 最小定理在信息学竞赛中的应用》周冬。

平面图的对偶图：把平面图的面当点，连接两个面的边当两个点的边的图。平面图有不错的性质：

• 欧拉公式：顶点数 $ + \(面数 \) - \(边数 \) = 2$
• 平面图的对偶图也是一个平面图

对一个源汇点都在无界面的边界的网络，如何根据平面图求它的最小割？我们从 \(S\) 到 \(T\) 连接新边创建出附加面，并对这个图创建对偶图，其中 \(S'\) 和 \(T'\) 为对偶图在附加面与无界面的点。则我们画个图就能发现，$S' \(到 \) T'$ 的一条路径就是原图的一个割。因此原图的最小割相当于新图的最短路径。

我们得到一个感受：当原问题不好入手时，考虑它的对偶问题。

### 最大权闭合图

这类题目是求具有依赖关系的最大权子图：选择 A 会有一定权值，但同时要选择 B 和 C，它们也会产生权值，这样的关系构成一张有向图。选择有向图的一个子图，使得若 \(v\) 在点集，则 \(v\) 的出边指向的点也在点集。

对这类题目的详解在论文有。此处只阐明算法：

1. 对原图的所有边容量赋为 \(\infty\)
2. 从 \(S\) 向正权点连权值为 \(w\) 的边
3. 从负权点向 \(T\) 链权值为 \(-w\) 的边
4. 最大权闭合子图 = 正权点权和 - 新图最小割

## 二分图最大匹配

二分图本身就有一个两端属于不同点集的边集，因此二分图常常被询问最大匹配。最大匹配即，选定一个边集，使得边集中的所有点不相交。二分图的最大匹配有 \(\mathrm{O}(nm)\) 的匈牙利算法（Hungarian Algorithm），非二分图的最大匹配需要带花树算法（Blossom Algorithm）。

不加注释地给出匈牙利算法代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool vst[N];int lnk[N];
bool DFS(int u){
    for(int v=1;v<=nV;v++)
        if(g[u][v]&&!vst[v]){
            vst[v]=1;
            if(!lnk[v]||DFS(lnk[v])){
                lnk[v]=u;
                return 1;
            }
        }

    return 0;
}

int ans=0;
for(int i=1;i<=nV;i++){
    memset(vst,0,sizeof(vst));
    if(DFS(i))ans++;
}

这个算法给出的是邻接矩阵做法，我们可以很轻易地改为邻接表。需要注意的点：

• 每次开始搜索前，清空访问数组
• 只有没有访问的节点可以操作

## 图的性质

明确以下概念：

• 点相关
  • 最小点覆盖
  • 最大独立集
  • 最小点权覆盖
  • 最大点权独立集
• 边相关
  • 最小边覆盖
  • 最大匹配

这些概念都可以在论文中找到具体定义，但我们重点讨论它们的性质：

• 最大匹配数 \(+\) 最小边覆盖数 \(=\) 顶点数（条件：联通图）
• 最大独立集 \(+\) 最小点覆盖数 \(=\) 顶点数
• König 定理：最大匹配数 \(=\) 最小点覆盖（条件：二分图）
• 最大流 \(=\) 最小割
• 最小割 \(=\) 最小点权覆盖集（条件：二分图）
• 最小点权覆盖集数 \(+\) 最大点权独立集数 \(=\) 顶点数（条件：二分图）

大部分性质都可以概括为：最值 $ = \(最值，最小 \) + \(最大 \) = ​$ 顶点数。后三条可以得到一个计算最大点权独立集的有效算法。具体的讨论和证明可以参考《两极相通 —— 浅析最大 — 最小定理在信息学竞赛中的应用》周冬。

## 最小费用最大流

给网络中的每一个边一条边权，求使得最大流的情况下的最小费用。下面不加注释地给出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

struct Dinic{
    struct Edge{int v,w,res;};
    vector<Edge> edg;
    vector<int> a[V];
    int st,ed;

void AddEdge(int u,int v,int w,int cap){
    edg.push_back((Edge){v,w,cap});
    edg.push_back((Edge){u,-w,0});
    int siz=edg.size();
    a[u].push_back(siz-2);
    a[v].push_back(siz-1);
}

int dis[V],pa[V],det[V];
bool SPFA(){
    static int inQ[V];
    memset(inQ,0,sizeof(inQ));
    memset(dis,0x3f,sizeof(dis));
    deque<int> q;q.push_back(st);
    dis[st]=0,inQ[st]=1,det[st]=INF,pa[st]=-1;

    while(!q.empty()){
        int u=q.front();q.pop_front();inQ[u]=0;
        for(int i=0;i<a[u].size();i++){
            Edge &e=edg[a[u][i]];
            if(e.res>0&&dis[e.v]>dis[u]+e.w){
                dis[e.v]=dis[u]+e.w;
                det[e.v]=min(det[u],e.res);
                pa[e.v]=a[u][i];
                if(!inQ[e.v]){
                    if(!q.empty()&&dis[q.front()]>=dis[e.v])q.push_front(e.v);
                    else q.push_back(e.v);
                    inQ[e.v]=1;
                }
            }
        }
    }

    return dis[ed]!=INF;
}

void Augment(int &w){
    w+=dis[ed]*det[ed];
    int u=ed;
    while(u!=st){
        edg[pa[u]].res-=det[ed];
        edg[pa[u]^1].res+=det[ed];
        u=edg[pa[u]^1].v;
    }
}

int MaxFlowMinCost(){
    int ret=0;
    while(SPFA())Augment(ret);
    return ret;
}

要点：

• 增广过程与 SPFA 相似，但仍要注意只有有残量的边可以通过。
• SPFA 过程注意是否出队入队，是否取消标记，是否入对位置正确。

### 费用流拆边

一条边所花费的费用是随流量线性增长。如果呈二次增长，甚至三次增长呢？需要拆边。

假设 $f \(为流量，\)cap \(为边容量，\)w = f ^ 2 \(为费用，则当 \) f = 1 \(时 \) w = 1 \(，\) f = 2 \(时 \) w = 4\(，\) f = 3 \(时 \) w = 9 \(。我们把边拆为 \) cap $ 条，每条容量是 \(1\)，费用分别是 \(1,3,5,\dots\) 则不难发现在流量相同时，费用会选择最小的 $ f \(条，而这 \) f \(条的费用加起来刚好为 \) w= f ^ 2$。当流量呈更复杂的多项式时，可以利用导数将边拆分。但很明显拆边有前提：流量必须是整数，多项式导数必须递增。

### 带权二分图匹配

如果有权，则可以给边赋权用费用流求解匹配。从 \(S\) 向 \(X\) 集合、从 \(Y\) 集合向 \(T\) 连权值为点权、容量为 \(1\) 的边，跑最大流最小费用即可。

## 练习

### 最大流

####USACO4.2.1 草地排水

最大流模板题目。

####BSOJ1721 上下界可行流 & BSOJ1723 上下界最大流 & BSOJ1725 上下界最小流

上下界网络流的练习题。

####BSOJ2547 网络流 24 题 - 6 最长递增子序列

第二问可以考虑每个点只能被选一次，并且假设当前节点结尾的 LIS 为 $ d \(，则当前节点只能向后面 LIS 为 \) d + 1 $ 的节点（否则不是 LIS）连容量为 \(1\) 的边。最后 $ S \(连 \) d $ 为 \(1\) 的点，$ d \(为全局 LIS 的点向 \)T\(连，跑最大流即可。第三问只需要修改部分点流量为 \)$。

####SDOI2015 星际战争

二分答案判断最大流是否足够。注意精度。

### 二分图最大匹配

####SCOI2015 小凸玩矩阵

二分答案 \(ans\)，\(X\) 集合为行，\(Y\) 集合为列，选中一个元素等于匹配两个点，每次只能选择小于等于 \(ans\) 的元素。判断这些元素（匹配）是否有 $ (n - k + 1) \(个。注意第 \)k\(大而不是第 \)k$ 小。

####USACO2005NovGold Asteroids

有行星的位置连接一条边，求最小点覆盖。可转化为最大匹配。

####USACO2005JanGold 泥泞的牧场

注意到每个点只能被横行或纵列覆盖（可以同时覆盖）。对于连续的泥泞，我们一块木板盖上是最好的。因此我们可以把图分块。横向的分块与纵向的分块编号后，一个泥泞就只能对应一条横向与一条纵向分块的交点了。

题目相当于转化为选择尽量少的分块，使得每个交点都被覆盖。如果把分块变成左右两端的点，交点变为它们之间的边，则原题目化为最小点覆盖。为什么可以转化？我们发现两个块要么有交点，要么没交点，并且只有横向块与纵向块相交，这完全符合二分图性质。

####BSOJ1775 xinyue 的约会

同上，但需要考虑有些边不需要添加。

####BSOJ2569 网络流 24 题 - 3 最小路径覆盖

把每个点拆成入点和出点，这样一个匹配就是一个边。在匹配中，每一个点的前驱和后继是唯一的，而只有起点不存在前驱，终点不存在后继。有多少个点没有前驱或后继，就有多少条路径。因此对于一个匹配，其路径数 = 点数 - 匹配数。

因此，最少路径 = 点数 - 最大匹配。

有关路径的问题可以将其拆成二分图，再观察路径的性质。

### 最小割

最小割的题目算是比较有价值，也是比较难转换的模型题目。

####POJ2125 Destroying the Graph

每条边可以被入点破坏也可以被出点破坏。因此构造二分图求最小割。

####POJ3469 Dual Core CPU

考虑没有额外代价的情况，则一个任务只能在两个 CPU 的其中一台运行。这个就是最小割模型，$S \(向任务 \) i \(连边权为 \) a_i\(的边，\)i \(向 \) T \(连边权为 \) b_i\(的边，则最小割就把所有点集分成两个部分（要么属于 \) S \(，要么属于 \) T $），且使得所有割边代价最小。

考虑加上代价。我们希望当 $ a \(与 \) b \(不在同一个点集时能有额外的权 \) w _i\(，这很像最小割的定义，因此我们考虑把 \)w_i\(也加入到最小割。具体做法是在 \) a \(与 \) b \(之间连边权为 \) w_i\(的无向边，这样当 \) a \(与 \) b $ 在同一个集合时此边不会是割边，而不在同一个集合时，会把额外代价计算。这就解决了问题。

往往要从定义出发：割边是连接两个属于不同集合的点的边集。下面的题目也显示出这个特点。

####SPOJ839 Optimal Marks

我们发现因为存在位运算，所有边权的总和最小等价于边权的每一位总和最小。因此单独考虑每一位，且每一位都只有 $ 0$ 和 $1 $ 可以取。注意到 xor 的定义是两个数不同则为 \(1\)，相同为 \(0\)，边权只有端点的两个数不同时才被计算，这和最小割的定义同样很像。

因此最小割模型显然。把两个集合当成选择的值，向每个点连接容量为 \(\infty\) 的边，有边相连的两个点连容量为 $ 1 \(的边。这么做的目的是：割边只能在 ** 特定的边 ** 取到，而不能在 ** 容量为 **\)$ 的边取到。对每一位跑一次最小割即可。

我们得到一个直观的感受：如果一条边不想成为割边，只需要把容量设为 \(\infty\) 。

####ZJU2676 Network Wars

见论文。此处重点讨论细节。

对给定网络，我们需要选出一个最小割集。由于分数规划使得边权可能为负，而负边权相当于反边，是不会被计算在最小割的容量的，因此需要手动叠加，而只对边权 $ > 0 $ 的边求割。

####BSOJ2550 网络流 24 题 - 9 方格取数问题

对棋盘黑白染色后发现相邻的不同颜色点之间只能选择其中一个。因此把有冲突的点连边，求最大独立集（权为 \(1\) 的最大点权独立集）即可。注意是二分图，转化求最小点权覆盖集 \(\to\) 最小割 \(\to\) 最大流。

####CQOI2017 老 C 的方块

题目描述很复杂，大致就是在一个特殊的网格上不能有特定图形出现，而去除一个网格需要一定费用。

然后我们观察四个图，发现特殊边两侧刚好连接两个格子。“某些状态不能共存，而去掉某个状态需要一定代价” 的想法让我们想到最小割（虽然数据范围上不是这样的）。因此有这些形状的格子要连接起来，并且至少有一个连接源点或汇点。经过一番构图，我们构造出下面这种网络：

\[ \begin {matrix} \vdots & &\vdots & &\vdots & &\vdots & &\vdots & &\vdots\\ \downarrow &\Leftarrow &\leftarrow &\leftarrow &S & &T &\leftarrow &\leftarrow &\Leftarrow &\leftarrow &\cdots\\ \downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow &\\ T & &S &\rightarrow &\rightarrow &\Rightarrow &\rightarrow &\rightarrow &T & &S &\cdots\\ \uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow &\\ \uparrow &\Leftarrow &\leftarrow &\leftarrow &S & &T &\leftarrow &\leftarrow &\Leftarrow &\leftarrow &\cdots\\ \downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow &\\ T & &S &\rightarrow &\rightarrow &\Rightarrow &\rightarrow &\rightarrow &T & &S &\cdots\\ \uparrow & &\downarrow & &\uparrow & &\downarrow & &\uparrow & &\downarrow &\\ \uparrow &\Leftarrow &\leftarrow &\leftarrow &S & &T &\leftarrow &\leftarrow &\Leftarrow &\leftarrow &\cdots \end {matrix} \\ \text {（有没有想到洋流图）} \]

每个交点是原图中的一个方块，双线箭头代表图中的特殊边。我们在这张网络图上能发现原图中的四种方块都对应一条从 \(S\) 到 \(T\) 的边，我们只需要求最小割就是最小花费。问题是怎么设置边权。

明显处于 \(S\) 和 \(T\) 上的点应该各自连 \(w\) 到 \(S\) 或 \(T\)，那特殊边两侧的两个方块呢？如果要删掉一个方块，则只需要删掉一个就好了，两个同时删是不划算的。因此我们只需要给特殊边设两个方块的较小 \(w\) 即可。

虽然本题点的规模达到了 \(10^5\)，但棋盘很大，连边只在相邻的方块出现，因此边数不大。跑跑最大流就过了。

是道建图好题。我们可以得到一个直观感受：最小割可以解决不共存的最小代价问题。这跟上面利用割的定义最小化分点代价不同，其出发点是源汇点的联通性。

### 最大权闭合图

####BSOJ2543 网络流 24 题 - 2 太空飞行计划

很明显的最大权闭合图模型，直接转化。

####NOI2006 最大获利

见论文。选定一个边同时要选定两个点，转化模型。

####TJOI2015 线性代数

转化题目后发现相当于有许多物品，要得到物品 $ i \(和 \) j \(需要先选定 \) i \(和 \) j\(，而选定 \) i \(和 \) j$ 都需要代价。接着就可以做了。

有个神奇的做法是暴力寻找不要什么物品，时间复杂度 $ (n ^ 3 n)$，跑起来还挺快。

### 费用流

####BSOJ4914 疯狂的方格取数

拆点。由于网络流与边有关，因此和点有关的题目往往需要把点拆掉来建立边。

####ZJOI2010 网络扩容

第一个最大流很简单。

第二个我一开始估计是在残余网络上操作，然后跑个 DP 计算每条路径扩展 k 所需要的费用，再统计和即可。不过这不好实现还容易 TLE。发现所需费用是费用流的表达式，但是如果直接跑费用流，我们希望有容量的边不计算权值，没流量的边计算权值，怎么办？

残余网络中，原图都加一条边权为 \(w\)，容量为 \(\infty\) 的边。再从超级源点 \(s\) 向 \(1\) 建边权为 \(0\)，容量为 \(det\) 的边。这样，在跑费用流的时候，如果一个边有流量就会优先选择这条没有花费的边，否则只能选择有花费的新边。

这个思路挺巧妙的，虽然我觉得对 \(n=1000,m=5000\) 的数据跑 \(\mathrm{O}(n^2m)\) 有点夸张。不过据说 Dinic 的复杂度和 SPFA 一样是个迷，因此还是可以跑的。

####SCOI2007 修车

本质上是一个打水问题，不过在不同的维修队列里花费时间也不一样。

费用流模型不难想到，可是具有后效性。然而我们发现把每个维修人员的

【未完成】

####NOI2008 志愿者招募

题目太神，不会做。但是还是放上 BYV 的题解。

具体的思路是把不等式添加变量修改为等式，这样容易思考。其次发现每个人都从某段时间开始，某段时间结束，可以考虑到差分。两者结合就得到了新的等式，并且由于差分的特性，每个有关变量都刚好出现两次且符号相反。

啧啧称奇。（虽然我不知道为什么推出来之后，需要求最大流。）

## 总结

网络流通常用来求一类有限制（选择次数、不可同选）的题目。建模相比起算法往往更重要，因此如何构造网络是网络流题目的一个重点。

• 需要掌握图的点与边集关系，尤其是二分图
  • 最大匹配数 \(+\) 最小边覆盖数 \(=\) 顶点数（条件：联通图）
  • 最大独立集 \(+\) 最小点覆盖数 \(=\) 顶点数
  • König 定理：最大匹配数 \(=\) 最小点覆盖（条件：二分图）
  • 最大流 \(=\) 最小割
  • 最小割 \(=\) 最小点权覆盖集（条件：二分图）
  • 最小点权覆盖集数 \(+\) 最大点权独立集数 \(=\) 顶点数（条件：二分图）
• 网络流的建模入手点
  • 有关选择的依赖关系的问题，可以考虑最大权闭合图
  • 有关路径的问题可以按照出边入边将其拆成二分图，再观察路径的性质
  • 有关等式或不等式，考虑流量平衡（如上下界网络流、志愿者招募）
  • 有关不共存的最小代价，考虑最小割使源汇不联通的性质，在不共存状态间连边，再与源汇连边求最小割

东西很分散，知识比较乱，因此就放在一起写了。

素性判断

Rabin-Miller

单次时间复杂度为 \(\mathrm{O}(\log n)\) 的判素方法。当底数枚举范围为 \((1,p]\) 时，正确概率为 \(1-\left(1/4\right)^p\)。OI 中一般测试 4~5 次就足够了。原理是利用了费马小定理，具体的探究见 Matrix67 的素数与素性测试。

1. 将待测试数 \(x\) 化为 \(x-1=a*2^p\) 的形式；
2. 选择一个 \([2.n)\) 间的底数 \(bas\)，对每个底数 \(bas\) 考察：
   1. 计算 \(x'=bas^{a*2^p}\bmod{x}\)；
   2. 分类讨论：
      • \(x'=1\)。令 \(p'=\frac p2\)，继续考察 \(bas^{a*2^{p'}}\pmod{x}\)；
      • \(x'=x-1\)。则 \(x\) 为 \(bas\) 下的伪素数，考察下一个底数；
      • 否则 \(x\) 为合数，退出算法。

附上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

bool RabinMiller(ll n){
    if(n==2)return 1;
    if(n<=1||!(n&1))return 0;

    int p=0;ll a;
    while((n-1)%(1<<(p+1))==0)p++;
    a=(n-1)/(1<<p);

    for(int i=1;i<=UPP;i++){       //UPP为测试次数
        int bas=rand()%(n-2)+2;
        for(int j=p;j>=0;j--){
            ll tmp=QPow(bas,a*((ll)1<<j),n);
            if(tmp==1)continue;
            else if(tmp==n-1)break;
            else return 0;
        }
    }

    return 1;
}

实际运用中还是很快的。

Eratosthenes 筛法

NOIP 知识点。直接放代码。

1
2
3
4
5
6
7

void Eratosthenes(){
    int upp=sqrt(N);
    for(int i=2;i<=upp;++i)        //大于sqrt(N)的数已经被筛过了
        if(!notPri[i])
            for(int j=i*i;j<N;j+=i)      //小于i^2的数已经被筛过了
                notPri[j]=1;
}

值得注意的是我不止一次没注意筛法的上下界，使得复杂度变大。（其实也没有多慢）

线筛

欧拉函数

欧拉函数 \(\Phi\) 是积性函数，因此可以线性筛。

代码：

1
2
3
4
5
6
7

void Phi(){
    for(int i=1;i<N;++i)phi[i]=i;
    for(int i=2;i<N;++i)
        if(phi[i]==i)
            for(int j=i;j<N;j+=i)
                phi[j]-=phi[j]/i;
}

单个 \(\Phi\) 值只需要利用 \(\Phi(n)=\Pi_{i=1}(1- \frac 1{p_i})\) 即可。注意需要特判大于 \(\sqrt{n}\) 的因子。

1
2
3
4
5
6
7
8
9
10

int Phi(int x){
    int ret=x，upp=int(sqrt(x)+1);
    for(int i=2;i<=upp;++i)
        if(x%i==0){
            ret-=ret/i;
            while(x%i==0)x/=i;
        }
    if(x>1)ret-=ret/x;
    return ret;
}

欧拉函数的一些性质

由辗转相除法可以得：

\[(a,b)=(a,a+b)=(b,a+b)\]

\(\varphi (n)\) 求的是 \([1,n]\) 中 \((i,n)=1\) 的个数，若 \((i,n)=1\)，则 \((n-i,i)=1\)，即互质的数是成对存在的。因此 \([1,n] (n>1)\) 中与 \(2n\) 互质的数有 \(\varphi (n)/2\) 个。

由上述结论容易得到：

\[ \sum _{i=1,\ (i,n)=1}^n = \frac {n\times \varphi(i)}2 \quad (n>1)\]

一些内容可以参考关于欧拉函数及其一些性质的美妙证明（2）。

指数循环节

考虑这么个式子：\(a^x\equiv c\pmod{p}\)。如果 \(x\) 很大就不能直接求了。

明显 \(p\) 为质数时，根据费马小定理有：

\[ a^x \bmod{p} = a^{x \bmod \phi(p)} \bmod{p} \]

然而 \(p\) 是合数也有结论：

\[ a^x \bmod{p} = a^{x \bmod \phi(p)+\phi(p)} \bmod{p}\quad (x\geq\phi(p)) \]

注意有条件，不能直接用（虽然通常可以）。

原根

待补

欧拉定理

待补

扩展欧拉定理

待补，但是其实上面给出式子了。

离散变换

和模运算有关。模运算除了除法外，四则运算都可以先模再运算最后模。除法需要找逆元。

逆元

\(x\) 在 \(p\) 下存在逆元的充分必要条件是 \((x,p)=1\)。

逆元的求法：

• 扩展欧几里得（求解 \(a*inv+p*y=1\)）
• 费马小定理（\(a^{\Phi (p)}\equiv 1\pmod {p} \Rightarrow inv=a^{p-2}\ \text {（p 为素数）}\)）
• 线性递推逆元表（\(inv_i=\left(p-\lfloor \frac pi \rfloor \right)* inv_{p\bmod{i}}\bmod{p}\)）

第三个很玄学就是了。简单证明帮助理解：

令 \(p=nt+k\)，则：

\[ \begin{aligned} nt+k&\equiv 0\pmod{p} \\ \Rightarrow k&\equiv -nt\pmod{p} \\ \Rightarrow n^{-1}&\equiv -tk^{-1}\pmod{p} \\ \Rightarrow n^{-1}&\equiv -\lfloor{\frac pn}\rfloor *(p\bmod{n})^{-1}\pmod{p} \end{aligned} \]

即 \(inv_i=\left(p-\lfloor \frac pi \rfloor \right)* inv_{p\bmod{i}}\bmod{p}\)。

但是这个东西有点难背。我们是不是可以 \(\mathcal{O}(n)\) 求阶乘，可以 \(\mathcal{O}(\log n)\) 求 \((n!)^{-1}\)，可以 \(\mathcal{O}(1)\) 求 \(n^{-1} = (n-1)!/n!\) 呢？

好了，现在我们找到一个 \(\mathcal{O}(n + \log n)\) 求 \([1,n]\) 逆元的方法了。

离散对数

其实就是求解 \(a^x\equiv b \pmod{p}\)。根据费马小定理，对于 \(p\) 为质数的情况，\(i\) 取 \([0,p)\) 时恰好使得 \(a^i\bmod{p}\) 取到 \([0,p)\) 的值各一次。因此此方程若有解，则一定在 \([0,p)\) 内有且仅有一解。

Baby-step Giant-step

求解这个方程的大步小步算法（Baby-step Giant-step）可以参考训练指南。这里只描述框架。

1. 令 \(m=\sqrt{p}\)，用哈希表或 map 记录取得 \(a^i\bmod{p}\ (0\leq i<m)\) 时 \(i\) 的最小值；
2. 对 \(a^{j \times m}\ (1\leq j\leq m)\) 查找表中是否存在 \(b*a^{-m}\bmod{p}\) 对应的 \(i\) 值：
   • 存在。则最小解为 \(x=j*m+i\)；
   • 不存在。考察下一个 j。

时间复杂度为 \(\mathrm{O}(\sqrt{n})\)。然而使用 BSGS 的前提条件是 \((a,p)=1\)，当 \(p\) 不是质数的时候不一定能使用（但是 \(p\) 为质数时必须有 \(a<p\)，否则也不保证 \(a\) 不为 \(p\) 的倍数）。好在我们可以使用扩展 BSGS 来解决 \(p\) 不是质数的情况。

1
2
3
4
5
6
7
8
9
10
11

int BSGS(ll a,ll b,ll p){
    map<ll,int> s;
    int m=(int)ceil(sqrt(p));
    ll tmp=1;
    for(int i=0;i<m;i++,tmp=tmp*a%p)
        if(!s.count(tmp))s[tmp]=i;
    ll inv=Invert(tmp,p);tmp=b;
    for(int i=0;i<m;i++,tmp=tmp*inv%p)
        if(s.count(tmp))return i*m+s[tmp]+1;
    return -1;
}

扩展 Baby-step Giant-step

我们不能求解的原因是费马定理不一定再适用，但可以通过不断对 \(a\) 和 \(p\) 提取 GCD 的方法使得 \((a,p)=1\)，再应用 BSGS。

明确这么一件事：令 \(g=(a,p)\)，则 \(a^x\equiv b\ \pmod{p} \Leftrightarrow \frac ag \times a^{x-1}\equiv \frac bg \pmod{\frac pg}\)，具体理由可以展开为不定方程后同除 \(g\) 即可。这样就可以通过不断除 \((a,p)\) 使得 \((a,p)=1\)。流程：

1. 当 \(g=(a,p)\not =1\)，化方程为 \((\frac ag) \times a^{x-1}\equiv \frac bg\ \pmod{\frac pg} \Rightarrow a^{x-1}\equiv \frac bg \times (\frac ag)^{-1}\ \pmod{\frac pg}\)；
   • 若 \(b\) 已经为 \(1\)，则 \(x\) 为除以 \(g\) 的次数（特判）；
   • 否则操作直到 \((a,p)=1\)；
2. 使用 BSGS。

注意特判是需要的，因为当 \((a,p)\not =1\) 时也有可能存在解 \(x\)，而继续操作会使得 \(x\) 增大。

同余方程

即求解 \(ax+by=c\)，也可以转化为 \(ax\equiv c\ \pmod{b}\)。

扩展欧几里得

求解方法是扩展欧几里得，有解的充分必要条件是 \((a,b)|c\)，求解的结果 \(x_0,y_0\) 是最小化 \(|x|+|y|\) 的一组解。由于比较模板，就直接放上代码了。

1
2
3
4
5

void ExtendGCD(int a,int b,int &x,int &y,int &g)       //x和y都是传引用
{
    if(!b)x=1,y=0,g=a;
    else ExtendGCD(b,a%b,y,x,g),y-=x*(a/b);      //x和y要交换，a/b必须要向下取整
}

时间复杂度和欧几里得一样，可以近似看作 \(\mathrm{O}(\log{n})\)。

求解的是 \(ax+by=(a,b)\) 的解。以下我们对变量带上 \('\) 符号时表示该值为原值除以 \(g\)，则明显原问题的解为 \(x=x_0 \times c',y=y_0 \times c'\)。

要求出其他的解，则只需要迭代 \(x=x_0+b',y=y_0-a'\) 即可。这个结论可以通过假设一组其他解 \(x,y\) 和 \(x_0,y_0\) 联立解得。我们往往要求 \(x\) 的最小非负解，根据这个结论我们可以得到 \(x_+=(x_0\bmod{b'}+b')\bmod{b'c'}\)。

欧几里得

由辗转相除法可以得：

\[(a,b)=(a,a+b)=(b,a+b)\]

这个结论我也不知道有什么用，但是看起来可以化简一类累和 GCD 的问题。如 SDOI2008 沙拉公主的困惑 处理了 \((M! , i) = (M! + i , i) \ (1<i \leq M!)\)，使得一个大数 \(N!\ (N>M)\) 可以被分解成多段长度为 \(M!\) 的段，从而降低了求 \(N!\) 与 \(M!\) 中互质的二元组数的困难。

另一个例子见这场比赛的 I 题。

类欧几里得

震惊了，还有这种算法。等省选结束学习一发。

中国剩余定理

对于单组同余方程 \(ax\equiv c\pmod{p}\) 求解，我们可以使用扩展欧几里得。但对于多组同余方程 \(x\equiv c_i\pmod{p_i}\)，我们需要中国剩余定理（Chinese Remainder Theorem）。

假设有 \(n\) 个方程组，且 \(M=\prod p_i,m_i=\frac M{p_i}\)。我们考虑其中的一个方程 \(x\equiv c_i\pmod{p_i}\)。由于 \((m_i,p_i)=1\)，因此方程 \(m_ix+p_iy=1\) 有解。我们对这个方程两边同模 \(p_i\)，并且令 \(e_i=m_ix\)，则有 \(e_i\equiv 1\pmod{p_i}\)。

根据一些神奇的方法构造出一个解 \(x=\sum_{i=1}^n c_ie_i\)。观察这个式子，我们给两边同除 \(p_i\)，则只剩下 \(x\equiv c_ie_i \equiv c_i\pmod{p_i}\)，即原模方程组。然后就可以通过扩展欧几里得得到 \(x\) 的一个解了。

扩展中国剩余定理

用于解决不互质的情况。

假设任意两个方程组 \(x\equiv c_1\pmod{p_1},x\equiv c_2\pmod{p_2}\)，化为方程组：

\[ \begin{cases} x=c_1+k_1p_1 \\ x=c_2+k_2p_2 \\ \end{cases} \]

联立得 \(c_1+k_1p_1=c_2+k_2p_2\)，可以解不定方程得到 \(k_1,k_2\) 的一组解 \(k_1',k_2'\)，因此 \(k_1=k_1'\frac{a_2-a_1}g+T\frac {p_2}g\)，\(T\) 为任意整数。回代入任意一个 \(x\) 的方程得：

\[ \begin{aligned} x=&c_1+p_1k_1 \\ =&c_1+p_1(k_1'\frac{a_2-a_1}g+T\frac {p_2}g) \\ =&c_1+p_1k_1'(\frac{a_2-a_1}g+T\frac {p_1p_2}g) \end{aligned} \]

即 $xc_1+p_1k_1'g \(，两个方程组合并为一个方程组。需要合并最多 \)n-1\(个方程组，时间复杂度 \)(n)\(。注意 \)x$ 可能会很大，一般化为最小非负解再计算。

用这个方法也可以推出非扩展情况，然而非扩展情况的形式推不出扩展情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

ll ExtendCRT(){
    ll a0,p0,a1,p1;bool flag=1;
    cin>>p0>>a0;
    for(int i=2;i<=n;i++){
        ll x,y,g,c;
        cin>>p1>>a1;
        if(flag){
            ExtendGCD(p0,p1,x,y,g);
            c=a1-a0;
            if(c%g){flag=0;continue;}
            x=x*(c/g)%(p1/g);
            a0+=x*p0;p0=p0*p1/g;
            a0%=p0;		//防止溢出
        }
    }
    if(flag)return (a0%p0+p0)%p0;
    else return -1;
}

这个代码可能是有问题的，在 POJ 过了，在 BSOJ 没过。然后我小叮当今天就要打爆你 CRT 的头

神奇小技巧

快速幂

NOIP 内容。时间复杂度 \(\mathrm{O}(\log{n})\)。

1
2
3
4
5
6

ll QPow(ll bas,ll t){
    ll ret=1;
    for(;t;t>>=1,bas=QMul(bas,bas))
        if(t&1)ret=QMul(ret,bas);
    return ret;
}

快速乘

这个就比较少见了。当两个数的乘法（取模）可能连 long long 都爆时，就可以用这个方法。其思想是将十进制乘法变为二进制乘法，并按位计算。由于乘数 \(b\) 每次只会翻倍，因此不会超出 long long。时间复杂度 \(\mathrm{O}(\log{n})\)。

ll QMul(ll a,ll b){
    if(a>b)swap(a,b);
    ll ret=0;
    for(;b;b>>=1,(a<<=1)%=p)
        if(b&1)(ret+=a)%=p;
    return ret;
}

练习

数论题目真是多而难写。很绝望。有些基础题真的水水的，就不放了。

Baby-step Giant-step

SDOI2011 计算器

操作 1 为快速幂，操作 2 为同余方程，操作 3 为离散对数。

SDOI2013 随机数生成器

通过对递推式进行迭代可以得到离散对数的方程，需要扩展 BSGS。但是题目需要多个分类讨论，比较复杂。

同余方程

NOI2002 荒岛野人

假设 \(M\) 个洞穴两个野人 \(t\) 天相遇，则有 \(pos_i+t \times det_i=pos_j+t \times det_j \pmod{M}\)，可以解不定方程。如果不相遇，则 \(t\) 应该大于两个野人寿命最小的那个，或者根本无解。

从小到大枚举 \(M\)，对每个 \(M\) 对任意两个野人判定是否可行即可。时间复杂度 \(\mathrm{O}(MN^2)\)，事实上到不了上界。

欧拉函数

SDOI2008 沙拉公主的困惑

由于辗转相除法 \((a+b,b)=(a,b)\)，因此 \((M!,i)=(M!+i,i)\)，即对于 \([1,N!]\) 的每一段 \(M!\)，与 \(M!\) 互质的个数都是一样的。我们知道与 \(M!\) 互质的个数为 \(\phi(M!)\)，因此答案 \(ans={N!*\phi(M!) \over M!}\)。

展开欧拉函数得：

\[ans=N!*\Pi_{i=1} (1-\frac1 {p_i}) \quad (p_i|M!\text {且} p_i\text {为质数})\]

不难发现 \(p_i\) 其实就是 \([1,m]\) 的所有质数，因此我们可以预处理出小于 \(n\) 的质数的 \((i-1)\over i\) 的积和 \(n!\)，就可以 \(\mathrm{O}(1)\) 回答询问了。

总时间复杂度 \(\mathrm{O}(max(n,m))\)。

快速乘 / 快速幂

BZOJ4766 文艺计算姬

根据矩阵树定理可以推得答案为 \(n^{m-1}*m^{n-1}\)，需要快速乘和快速幂。

也可以用 prufer 序列得到。

总结

数论是很神奇的东西，数论题是奥妙重重的题目。入手点一般在于将题目抽象为目标式、将目标式化简为高效可求式的过程。为此必须熟练掌握初等数论的内容特别是结论，以应对其中的数学变换。

当然猜测不出规律的时候可以打表观测说不定就猜对了。

（然后没有具体的总结，毕竟数论变化太多，需要结合题目看）