hk_cnyali's Blog

一些注意事项

Debug经常错的细节

比较基础,容易忽略的小细节

issue date
多组数据时链式前向星的ee记得清0
dfsdfs序有关的问题不要把dfn[x]dfn[x]写成xx
10x10^xx+1x + 1位数,dfsdfs的时候要注意return的条件
set中lower_bound需要写S.lower_bound(x),不能写成lower_bound(S.begin(), S.end(), x)
multiset中erase必须传迭代器,如果传键值的话会删除键值为当前值的所有数
map或set中迭代器只能++或--,而不能+1或-1,会编译错误
无向图链式前向星的数组一定要开到maxm2maxm * 2!!!(8.2 T2惨痛的教训) 18.8.2
gen记得srand(time(0))....
多个乘除间有整除的话要记得大括号!!!(e.g. (a/b)(c/d)a/bc/d(a/b)*(c/d) \ne a/b*c/d) 18.9.25
开O2的时候如果多次运行程序输出的值不一样,多半是某些局部变量没初始化 18.9.25 18.10.24
对负数取模会有问题!!! 18.10.06
遇到莫名其妙的错误的时候多半是数组开小或者局部变量没初始化,一道分块题调了我几个小时最后发现居然是数组开小...正式比赛一定要多用proc_status检查一下数组大小,防止RE或MLE 18.10.26 18.10.29
2322^{32}取模是unsigned int,不是unsigned long long 18.10.29
sort的cmp条件不能写\le,否则在相等的时候会RE 18.10.29
浮点数比大小的细节,具体见此 18.12.25
连等赋值时默认是从右往左处理,即如果是a = b = 1,它其实是a = (b = 1)这样处理的,所以不要写这样的代码:A[++cnt] = B[cnt] = sum,而应该写成++cnt, A[cnt] = B[cnt] = sum 19.1.3
不要对循环变量做一些奇怪的操作!!(如swap,赋值等) 19.3.2
只要不是void的函数必须要有返回值!!!否则会RE!!!可以通过fsanitize检查 19.3.6
__in128unsigned long long的范围差远了!!! 19.3.28
函数传参的时候一定要注意不要把LL传成int了!!!!! 19.6.23
STL若倒序遍历,使用rbegin的时候迭代器也是++,而不是-- 19.8.12
1.0 *转出来的类型是double1.0l *转出来的才是long double。有些时候会有精度问题 19.10.4
c++98中STL容器直接swapO(n)O(n)的,不是O(1)O(1)的!!! 19.10.23
注意位运算与==的优先级!!!例如 if ((a & b) == c) 这里就必须要打括号!!! 19.11.3
结构体lower_bound的时候传进去的东西一定要记得和结构体类型相同!!! 19.12.9
double数组不能memset (A, -0x3f, sizeof A),要手动赋值!!!!! 20.4.18

与算法有关的细节

issue date
FFT记得四舍五入,最好用round()round(),不要(int)(x+0.5)(int)(x+0.5)
快速乘要先将aabbmodmod取模并变成非负,否则可能会爆long long或者死循环
网络流初始化记得e=1 18.11.8 20.3.12
线段树在区间加法或是区间赋值的时候注意不要把(rl+1)(r - l + 1)写成(yx+1)(y - x + 1)
spaly中记得while(Tree[x].fa != y)而不是while(x!=y),然后要记得if(!y) root = x;
树状数组在addwhile(x <= maxn)maxn的范围一定要开够!!!!!
Hash初始化的时候mul[0]=1(muli=baseimul_i=base^i) 18.9.26
各种数据结构初始化的时候想清楚范围!!!(如并查集、树状数组等) 18.9.28
不知道为什么每次这种五子棋之类的模拟都会少考虑向左下↙斜着的对角线的情况... 18.10.10
实数二分的时候像rr->r1r-1这样的边界变化应该写成rr->repsr-eps 实数三分的时候除了判epseps之外还要判当前三分了多少次了,否则有可能会T 18.10.16 19.3.9
树剖在线段树中操作的时候记得传dfn[x]dfn[x]而不是xx 18.10.16
莫队在sort时右端点按照左端点所在块的奇偶性,从大到小/从小到大蛇形排序 18.12.15
LCT各种操作的时候要记得push_uppush_down!!! 18.12.30 18.12.31
树剖的dfn[]dfn[]写在第一个dfsdfs里去了... 19.1.2 19.1.3
长链剖分中动态分配内存的时候只要分配(maxdep[x]dep[x]+1)2(maxdep[x] - dep[x] + 1) * 2 19.1.7
NTT蝴蝶变换忘记取模。。。 19.1.9 19.1.10
DSU不路径压缩时写成return x == fa[x] ? x : fa[x]; 19.2.11
线段树开的范围写错。。。 19.2.11
点分治一定注意在计算答案的时候复杂度不能与nn有关,只能与当前子树有关 19.3.1
点分治注意在求当前size的时候,子树外的部分不要写成n - size[x],而应该是now_size - size[x]now_size表示当前联通块的大小 19.3.1
主席树调用的时候忘记加Root[] 19.3.3
优先队列默认是大根堆!!! 19.3.3
SAM各种数组一定都要开到maxn << 1!! 19.3.8
DAG的dp千万不能傻逼跑dfs。。。 19.3.11
kmp跳fail的时候是while,别写成if 19.3.17
模拟退火接受劣解的概率为eΔfTe^{\frac{\Delta f}{T}},其中Δf<0\Delta f < 0 19.4.5
二分图染色判断条件别写错。。。 19.5.11
带权并查集在link的时候一定要判断fx == fy!!! 19.5.17
多项式操作时一定要开static int F[Maxn], G[Maxn];!!!否则若干个多项式操作函数之间在相互调用时会相互影响 19.8.8 19.9.16
高斯消元的时候最后一定要有最后往回代的过程,否则会有影响消不掉 19.9.2
等比数列求和要特判公比为1的情况!!! 19.9.5
tarjan缩完点后要in_stk[x] = 0!!! 19.9.10
Dijkstra的时候一定要记得vis!!!不然复杂度是错的 19.9.30
setpii的时候一定要注意第二维的问题,如果第二维不参与排名的话最好设成0!!!(开车旅行这题就因为这个调了一年) 19.11.10
多项式求导、积分时要注意循环顺序问题 19.12.4
整除分块边界写成r <= n 19.12.13
分块中散块暴力的边界问题:for (int i = l; i <= min (r, R[x]); ++i) 19.12.17
有区间修改的线段树合并时要注意加一句:if (!x or !y) return 0; 否则0位置的值可能会改变 20.3.22
莫队端点移动时一定要想清楚!!!左右端点是反的,不要想当然!!! 20.5.11
LCT在pushdown的时候要记得把x点本身pushdown!!!!! 20.7.23

想题时的瓶颈/小trick

  • 逆向思维(考虑贡献)

  • 树上联通块个数==点数-边数 !!!!!!

  • 树上两点问题转换为两节点及其lca与树根的问题

  • 数对计算贡献时,老是想不清楚,总感觉会算重/算漏,或是会相互有影响、有限制,这时往往按照某种顺序或限制统计答案。例如:确定数对中较大的那个数,统计较小值的个数的贡献

  • 概率正着推,期望倒着推(虽然这句话已经被讲过很多遍了。。。)

    并且概率和期望的dp时方程的定义也略有区别。大概感性理解一下,一个是“到这里”,一个是“从这里开始”。这就对应了正着推和倒着推

  • 树上高斯消元把式子化成dp[x]=A[x]dp[fa[x]]+B[x]dp[x] = A[x]\cdot dp[fa[x]] + B[x]的形式,然后直接从下往上推即可

  • dp本质上就是把一个问题拆分成若干的部分,通过解决每个部分,再一步步拼成原问题。

    设状态时一开始要大胆去设,然后再通过观察去进行优化。

    优化可以从几个角度下手:

    1. 压缩状态量,减少状态的维度。
    2. 优化转移过程。常用方法有:数据结构维护(线段树、树状数组、平衡树等);FFT/NTT优化(可以见这里);决策单调性优化(斜率优化等)
    3. 如果发现一开始设的简单dp有问题的话,可以通过容斥/再dp预处理某一个东西来把它弄对。
    4. 直接dp不好计算的话可以考虑统计贡献
  • 看到异或、子段的字眼时要想到考虑前缀异或和

  • 树上问题求距离和时,可以考虑每条边对答案的贡献,否则如果考虑子树dp的话会比较复杂

  • 一些计数题需要考虑钦定最小的元素,以保证计数不重不漏

  • 联通块的计数问题考虑简单容斥,用总方案数减去不合法的方案数

  • 计数的时候可以先考虑去掉一些限制,然后再除掉/减掉一些方案数

  • 因为期望有线性性,所以期望题往往可以考虑两两点对的期望,即它们对答案的贡献;并且期望也可以容斥

  • 在挖掘题目性质遇到瓶颈时,可以通过暴力程序下手,多观察下程序,考虑如何去优化暴力,或者通过暴力把要求的问题抽象出来再考虑

  • 往前转移/前面对当前的贡献 不好考虑时,可以考虑考虑往后转移/对后面的贡献。 反之亦然

  • 对于每个位置找在它前一个/后一个比它大/小/满足某种条件的数往往用单调栈解决

  • 线段树维护区间最值

  • 退火

  • 一类比较常见的计数/容斥技巧:例如(1)iAi\sum{(-1)}^{i}A_i,可以考虑枚举ii的奇偶性以及AiA_i,通过dp,对于每个不同的AiA_i求出其方案数,有时还能直接把容斥系数考虑进去,不用讨论奇偶性

  • 统计序列上某些点对数时要考虑分治!!!

  • 很多计数题都是考虑最终状态, 分成若干个子问题,考虑每个子问题对答案的贡献

  • 既有点权又有边权可以考虑把某一个转化成另一个

  • 对于pkp^k型的计数问题(某个状态含kk个条件,则产生pkp^k的贡献),可以把pp拆到每个kk上,只要满足一个条件,就乘上pp,方便计数,9-10 T3

  • 计数时,如果存在关于数值大小关系的限制,而最终答案又与顺序无关的话,可以把数组排序,方便计数 ARC093 F9-6 T3已经没有什么好害怕的了

  • 贪心题决策很多很复杂时,要学会化简条件,把一般的情况化归到特殊的情况上去。比如某些决策可以同时/放在一开始考虑,并且不会使答案更劣

  • 计数时,什么东西是无标号的,那么就可以给它随便钦定一种顺序,形象地理解就是把它固定不动,再考虑另一个东西

  • dp的时候如果设考虑到第ii个的方案数不好计算的话,可以设考虑到第ii个,且强制第ii个满足某个条件的方案数P3084 [USACO13OPEN]照片PhotoCometOJ 70 C

  • 一个和堆有关的我见一次忘一次的问题:

    Q. 有两个长度都是 NN 的序列 AABB ,在 AABB 中各取一个数相加可以得到 N2N^2 个和,求这 N2N^2 个和中最小的 NN

    A. 把 AB 排序后,先把 A[1]+B[i]A[1] + B[i] 加入堆,每次取最小的出来,然后把 AA 那一维往后移一下

  • 当图论题暴力复杂度与度数相关时,考虑根号做法,即对于度数小于根号的点暴力,大于根号的点快速维护某些信息

  • 需要动态修改某一个位置的值的子集和 DP,可以做到根号:

    把一个二进制数砍成两半,修改时暴力枚举前半部分的超集修改;查询时暴力枚举后半部分的子集求和

  • 数论函数题,推式子推到没有办法优化的时候,可以考虑把某一层的枚举倍数重新转化成枚举约数(即把ddgg捆一起,枚举dgdg),可能会有意想不到的收获(19.12.13)

  • 矩乘技巧:

    1. 在倍增算答案的时候可以把 O(n3)O(n^{3}) 矩乘变成 O(n2)O(n^{2}) 矩乘,因为答案矩阵是一维的。

    2. 如果我们要多次询问 xnx^n 的值,而 x 是恒定不变的,可以通过预处理达到 O(1) 询问的复杂度。

  • 根据长度分类(根号平衡),大于TT的一个做法,小于TT的一个做法

    若数据范围中有"\sum一定"这样的字眼就要往这方面想

  • lca相关的计数/数据结构问题考虑枚举lca算答案 2-3毒瘤题

  • 给一个排列aia_i,以每个位置为右端点rr求出一个最大的lrl \le r,使得[l,r][l, r]中的元素权值也在[l,r][l, r]

    只要满足两个限制即可:

    1. i=lr(aii)=0\sum_{i=l}^{r} (a_i - i) = 0

    第一个限制只需要找到左侧第一个>r>r的元素,直接单调栈;第二个限制直接对aiia_i - i做前缀和,找到上一个前缀和相等的位置即可

  • nn个元素,每个元素可以取[1,m][1, m]的值,若nnmm大时,考虑枚举总共用了kk个值,设f(k)f(k)表示最多用kk个值的答案,g(k)g(k)表示恰好用kk个值的答案,然后容斥:

    g(k)=f(k)i=1k1(ki)g(i)\displaystyle g(k) = f(k) - \sum_{i=1}^{k - 1} \binom{k}{i} g(i)

  • 如果有nn个数,其线性基内元素可以异或出kk,则异或和为kk的方案数等于2nx2^{n - x},其中xx为线性基大小;否则为0

  • 看到和网格/矩形有关的计数时,考虑对每个1×11 \times 1的小格子/离散后的最小矩形统计贡献

  • 和序列、颜色相关的区间计数问题考虑每个元素随机赋权值,通过异或和转化成区间异或和等于0,然后简单统计

  • 多次询问的题只要没强制在线,都要往离线做法上想一下!!!

  • 二维(或更高维)的问题不好处理时,考虑能否把两维拆开/观察两维是否独立,从而简化问题

写代码的一些trick

  • 建图:网路流/需要清空的情况下用链式前向星,否则都用vector

    vector建图可以很方便删边、给边排序

  • 枚举子集技巧:for (int sub = state; sub; sub = (sub - 1) & state) 枚举超集技巧:for (int super = state; super <= ALL; super = (super + 1) or state)(这里因为格式问题打不出或,于是用or代替)

  • vector的unique:vec.erase (unique (vec.begin(), vec.end()), vec.end());

  • 平衡树:tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> T;

    查第kk小: T.find_by_order(k - 1)

    求排名: T.order_of_key (x)

  • 负数下标数组:

    1
    2
    int Pool[MAXN * 2 + 10];
    int *Dp = Pool + MAXN + 5;
  • INT_MAX是质数,可以当Hash模数,有逆元

考试注意事项

issue date
看清楚题目里有没有给出线段左端点大于右端点的情况 18.9.25
看清题目里给出的字符串的字符集 18.9.25
考试的时候不要手贱加#ifdef hk_cnyali!!!!! 19.1.7
gen的时候一定要多跑一些特殊边界情况,如值域比较大的情况、n和m不相等的情况 19.3.20
最后一定要检查空间、RE、以及MAXN有没有开够!!! 19.10.20
template 记得写DEBUG!!! 19.11.1

卡常技巧

  • const blabla &x

  • 矩阵乘法循环顺序i,k,j,可以判如果A[i][k] == 0continue;

    因为ans[i][j] += A[i][k] * B[k][j],这样的话ans[i][j]B[k][j]都是连续内存

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    inline Matrix operator * (const Matrix &rhs) const &
    {
    Matrix ans;
    memset (ans.A, 0, sizeof ans.A);
    for (register int i = 0; i <= D; ++i)
    for (register int k = 0; k <= D; ++k)
    {
    register int j = 0;
    LL tmp = A[i][k];
    if (!tmp) continue;
    for (; j <= (D - 5); j += 4)
    {
    Add (ans.A[i][j], tmp * rhs.A[k][j]);
    Add (ans.A[i][j + 1], tmp * rhs.A[k][j + 1]);
    Add (ans.A[i][j + 2], tmp * rhs.A[k][j + 2]);
    Add (ans.A[i][j + 3], tmp * rhs.A[k][j + 3]);
    }
    for (; j <= D; ++j) Add (ans.A[i][j], tmp * rhs.A[k][j]);
    }
    for (register int i = 0; i <= D; ++i) for (register int j = 0; j <= D; ++j) (ans.A[i][j] >= Mod) ? ans.A[i][j] %= Mod : 0;
    return ans;
    }

杂项

一定要注意题面中的数据范围!!!!!

要注意判边界情况!!!尤其是 n=0,n=1,m=0,m=1,k=0,k=1n = 0, n = 1, m = 0, m = 1, k = 0, k = 1 这样的情况!!!

多项式

  • 想要分治 + NTT的话,就必须要把答案写成这样的形式: ans=iF(i)\displaystyle ans = \prod_{i} F(i)

    即每个F(i)F(i)的地位要等价,否则不行。一般就把阶乘除过去就可以了

莫队

先把序列分块,把询问重新排序:belong[l]belong[l]为第一关键字,rr为第二关键字

看到区间问题,不要求在线就要往莫队上想

似乎这样的带权莫队复杂度也是正确的:每个数有权值wiw_i,一个数被加入/删除的复杂度为O(wi)O(w_i),保证wi=O(n)\sum w_i = O(n)。分块时按wi\sum w_i分,一旦当前的wi\sum w_i超过lim(=m(wi))lim(= \frac{m}{\sqrt(\sum w_i)})就立刻新开一个块

感性理解复杂度很对,若一个块大小很大,那序列长度就会很小

奇偶优化

左端点在奇数块内的询问,按rr递增排序

左端点在偶数块内的询问,按rr递减排序

回滚莫队

当莫队维护的数据结构只能加入、撤销而不好删除时的做法

其实就是每次询问完之后左指针回滚(撤销)到询问左端点所在块的右边界,总复杂度还会是正确的

但其实如果只能删除而不好加入也可以这样做,把排序方式换一下即可

带修莫队

相当于是(l,r,t)(l, r, t)三维的莫队

增加一根时间轴(与序列轴分开),询问按ll所在块为第一关键字,rr所在块为第二关键字,tt为第三关键字排序

先把llrr移到当前询问位置,然后移时间。移动过程中遇到的修改就执行(往右则应用,往左则撤销)

具体而言,判断修改的点是否在当前[l,r][l, r]内,若在则直接在数据结构上应用,否则更改序列轴上的值

三元环计数

无向图

重新定向成有向图,从度数小的点往度数大的点连边 (从大往小也可以)

枚举每条边(x,y)(x, y),再枚举yy的所有出点zz,若存在边(x,z)(x, z)(x,y,z)(x, y, z)为三元环

一个三元环会且仅会在度数最小的点xx处被统计到

复杂度是m×degym \times \sum{deg_y}的,而因为每个yy点的出边都m\le \sqrt m(若>m> \sqrt m,那它相连的那些点的出边都>m> \sqrt m,矛盾),所以总复杂度为O(mm)O(m \sqrt m)

有向图

因为无向图三元环个数最多O(mm)O(m \sqrt m),所以每次搜出来一个三元环判在原有向图中是否存在即可

四元环计数

还是考虑在度数最小的点处统计,但是不能转有向图了

注意需要保证xx是度数最大的点。将所有点排序,只要不满足就立刻break,复杂度就对了

线段树

  • 需要维护区间所有数是否相等,可以通过维护min、max判断。位运算要判断每一位的话可以维护or、and

  • 区间修改可以往势能分析上想

最小树形图

性质: 对有向图中每个点取一条入边,构成的图若无环,则为树形图

贪心,每个点选最小的那条入边。若存在环则缩环,新图中连向环的边的权值要减去该点在环上的入边权值(反悔型贪心)

重复上述过程直到无环

虚树

每次把关键点提出来重构成树(保持原树中的形态)。这样就可以支持一些与关键点和树形态相关的操作。最简单的例如求某个点到其他所有点的最短路等

双端队列

  • 滑动窗口维护区间最值时,考虑用双端队列维护。这个队列还是一个单调队列,头部是最优的元素,往后依次变劣。因为每个元素出现的时刻是一段区间,所以要这样维护

  • 同理,斜率优化的某种情况也如此。头部的元素当前最优,但后面某个时刻会变劣

容斥

  • 考虑一些非常规(无法直接使用通式)的容斥时,回归容斥的本质,直接对于一个方案考虑它总共被统计了多少次,要怎样才能使这个次数恰好为1

考虑贡献

计数不好统计的时候一定要想到考虑贡献!!!!!

圆方树

将仙人掌转化成树

tarjan缩点双(仙人掌中点双一定是环),把环上的边全删掉,而所有环上的点与新点相连

原图的点称为圆点,新建称为方点。

  • 方点一定不相邻

  • 圆点可以与多个方点相连,但只会有一个方点父亲(即一个点可以作为多次割点,但最多作为非割点出现一次)。这个性质很重要

分块

  • 看起来很奇怪的数据结构操作要想到分块!!

  • 预处理块到块的信息当时间/空间较劣时,尝试用ST表预处理优化

长链剖分

优化DP

用指针写,重儿子的指针指向该点 + 1的位置;轻儿子的指针新开

Code
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
int fa[MAXN + 5], len[MAXN + 5], son[MAXN + 5];

inline void dfs (int x)
{
for (int y : G[x]) if (y != fa[x])
{
fa[y] = x;
dfs (y);
if (len[y] > len[son[x]]) son[x] = y;
}
len[x] = len[son[x]] + 1;
}

int pool[MAXN + 5], *F[MAXN + 5], *top = pool;
int ans[MAXN + 5];

inline void dfs (int x, int fg) // fg: 该点是否为重儿子
{
if (!fg) F[x] = top, top += len[x];
else F[x] = F[fa[x]] + 1;

F[x][0] = 1;

if (son[x])
{
dfs (son[x], 1);
if (ans[son[x]]) ans[x] = ans[son[x]] + 1;
}

int mx = 0;
for (int y : G[x]) if (y != fa[x] && y != son[x])
{
dfs (y, 0);
Chkmax (mx, len[y]);
for (int i = 1; i <= len[y]; ++i)
F[x][i] += F[y][i - 1];
}

for (int i = 1; i <= mx; ++i) if (F[x][i] > F[x][ans[x]] || (F[x][i] == F[x][ans[x]] && i < ans[x])) ans[x] = i;
}

O(nlogn)O(1)O(n\log n) - O(1)kk祖先

长剖性质:任意点的kk祖先所在重链长度k\ge k

若它和kk祖先不在同一条重链上,则中间分叉的另一颗子树的最大深度不会更小

20-5-19-1

字符串哈希

调试:把base设成10

群论

Burnside引理

比较广义的形式

等价类数目等于所有置换的不动点数的平均值

一个置换的不动点数为:有多少个方案应用该置换后不变

Polya定理

link

FWT

DWT(A)i=j=0n1fi,j×aj\displaystyle DWT(A)_i = \sum_{j = 0}^{n - 1} f_{i, j} \times a_j

构造系数

原理: ff需满足 fi,j×fi,k=fi,jk\displaystyle f_{i, j} \times f_{i, k} = f_{i, j \otimes k}

  • and\mathrm{and}: fi,j=[i&j=i]f_{i, j} = [i \& j= i](即[ij][i\subseteq j]
  • or\mathrm{or} : fi,j=[ij=i]f_{i, j} = [i | j= i](即[ji][j\subseteq i]
  • xor\mathrm{xor}: fi,j=(1)popcount(i&j)f_{i, j}=(-1)^{popcount(i\&j)}

验证: 若iji \subseteq j, iki \subseteq k,则i(j  k)i \subseteq (j~|~k),显然成立。其余两个类似

DWT(A)i=f0,0×DWT(AL)i+f0,1×DWT(AR)iDWT(A)i+n2=f1,0×DWT(AL)i+f1,1×DWT(AR)i \begin{aligned} DWT(A)_i&=f_{0,0}\times DWT(A_L)_i+f_{0,1}\times DWT(A_R)_i\\ DWT(A)_{i+{n\over 2}}&=f_{1,0}\times DWT(A_L)_i+f_{1,1}\times DWT(A_R)_i \end{aligned}

IDWT: 把上式改写成等式左边为AL,ARA_L, A_R的形式

以异或为例:

DWT(A)i=DWT(AL)i+DWT(AR)iDWT(A)i+n2=DWT(AL)iDWT(AR)i \begin{aligned} DWT(A)_i&=DWT(A_L)_i+DWT(A_R)_i\\ DWT(A)_{i+{n\over 2}}&=DWT(A_L)_i-DWT(A_R)_i \end{aligned}

则可解出

数论函数

一些关系

  • μ1=ϵ\mu * 1 = \epsilon

  • Id=φ1φ=μId\mathrm{Id} = \varphi * 1 \Rightarrow \varphi = \mu * \mathrm{Id}

  • (μ×Id)Id=ϵ(\mu \times \mathrm{Id}) * \mathrm{Id} = \epsilon (\Big(这是因为 dnμ(d)d(nd)=[n=1]\displaystyle \sum_{d|n} \mu(d)d(\frac{n}{d}) = [n = 1] )\Big)

一些结论

  • n>1n > 1时,i=1n[(i,n)=1]i=nφ(n)2\displaystyle \sum_{i = 1}^{n}[(i, n) = 1]i = \frac{n *\varphi(n)}{2}

    证明在这里

  • d(i×j)=xiyj[(ix,y)=1]\displaystyle \mathrm{d}(i\times j) = \sum_{x | i} \sum_{y | j}[(\frac{i}{x}, y) = 1]

    σ(i×j)=xiyj[(ix,y)=1]xy\displaystyle \sigma(i\times j) = \sum_{x | i} \sum_{y | j}[(\frac{i}{x}, y) = 1]xy

    证明很简单 首先xxyy相乘一定是i×ji\times j的约数,但直接统计会算重
    考虑i×ji\times j的某个质因数pkp^{k},若iipk1p^{k_1}jjpk2p^{k_2}k=k1+k2k = k_1 + k_2
    再考虑由等式右边得到的合法数字,设其含ptp^{t}
    因为保证了(ix,y)=1(\frac{i}{x}, y) = 1,所以当tk1t \le k_1时,它全部来源于ii; t>k1t > k_1时,ii一定对其贡献了pk1p^{k_1}
    因此每个ptp^{t}只会被算一次

Prufer序

一个长度为n2n - 2,权值在[1,n][1, n]的数组。与nn个点的有标号无根树一一对应

nn个点有标号无根树个数为nn2n^{n - 2}

度数

nn个点的度数已经确定,为degideg_i,则方案数为(n2)!i=1n(degi1)!\displaystyle \frac{(n - 2)!}{\sum_{i = 1}^{n}(deg_i - 1)!}

扩展

nn个带权aia_i的点,边的权值为连接两点点权之积,树的权值为所有边权值之积,则所有树的权值和为

(i=1nai)×(i=1nai)n2 \Big(\prod_{i=1}^{n} a_i\Big) \times \Big(\sum_{i=1}^{n}a_i\Big)^{n - 2}
  • ai=1a_i = 1时,即为nn2n^{n - 2}

  • nn个点被分成mm个联通块,第ii个联通块大小为sis_i,则把所有联通块连成树的方案数为(i=1msi)×nm2\displaystyle \Big(\prod_{i=1}^{m}s_i\Big) \times n^{m - 2}

DP

  • 多重背包二进制拆分优化

pb_ds

1
2
3
tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> T;
T.order_of_key (x);
T.find_by_order (k - 1);

vimrc/template 易错

  • exec "!g++ % -o %< " .a:str
  • y0 y1,不是y1 y2
  • 忘记#define DEBUG(x)

SAM

  • 记得背板子

  • 考虑SAM中每个节点对答案的贡献!!

概率和期望

D(X)=E(X2)E2(X)D(X) = E(X^2) - E^2(X)

网络流

遇到暴力都很难写的题要考虑网络流/费用流!!

Dijkstra 费用流

目标是使 disdis 非负,且不改变原本性质

给每个点赋一个顶标 hih_i,一条原本 (x,y,w)(x, y, w) 的边变为 (x,y,w+hxhy)(x, y, w + h_x - h_y)。每跑完一次dij后,就把 hih_i 加上这次的 disidis_i

真正的最短路是 hh 而不是 disdis

对偶

20-7-19-4

20-7-19-5