一些要记住的小知识

  • $Fib_{n+m}=Fib_{n-1}Fib_{m}+Fib_{n}Fib_{m+1}$,见Link

  • 开$5000^2$的数组要检查空间大小,尤其是longlong

  • 如果要合并$n$颗线段树,值域为$k$,复杂度为$O(nlogk)$

  • 关于2-sat输出方案只需要管$bel[x \cdot 2]$和$bel[x \cdot 2 + 1]$的大小。

  • 同色球不相邻的方案计数问题可以按照每一种颜色分段考虑,见Link

  • 如果$a,b$在集合中,$(a+b)~mod~n$也在集合中(ab可以相等),如果$a$在集合中,那么$gcd(a,n)$的倍数都在集合中。
    证明:$$gcd(a,n)=ka-cn$$$$a \in Set$$$$ka \% n=gcd(a,n) \in Set\\ \forall p \cdot gcd(a,n) \% n \in Set$$

  • 如果$a,b$在集合中,$(a+b)~mod~n$也在集合中(ab可以相等),如果$a,b$互质,那么$0\sim n-1$都在集合中。
    证明:$$gcd(a,b)=1,gcd(a,b,n)=1\\ \forall k\cdot1 \% n\in Set \rightarrow [0,n) \in Set$$

  • 无向图欧拉回路判断:所有顶点的度数都为偶数。
    有向图欧拉回路判断:所有顶点的出度与入度相等。
    无向图欧拉路径判断:之多有两个顶点的度数为奇,其他顶点的度数为偶。
    有向图欧拉路径判断:至多有两个顶点的入度和出度绝对值差1(若有两个这样的顶点,则必须其中一个出度大于入度,另一个入度大于出度),其他顶点的入度与出度相等。 转自CSDN

  • 找欧拉回路的方法 转自CSDN

  • 重心的性质
  1. 树中所有点到某个点的距离和之中,到重心的距离和最小。
  2. 把两棵树通过一条边相连,新的树的重心在他们重心的连线上。
  3. 把一棵树添加或删除一个叶子,它的重心最多只移动一条边的距离。
  4. 一棵树最多有两个重心,且相邻。
  • 错排公式
    $$
    f[0]=1,f[1]=0\\
    f[i]=(i-1)\times (f[i-1]+f[i-2])
    $$
    考虑填入第$n$个数,此时有$(n-1)$种选择
    假设$n$填入的位置是$k$,那么有两种情况
    (1) $k$填入$n$位置,那么对于剩下的数的方案是$f[n-2]$(k已经错排)。
    (2) $k$不填入$n$,对于剩下的数的方案数是$f[n-1]$(k不考虑到错排里面)。

  • 树上高斯消元
    对于树DP,如果一个点可以从子树转移也可以从父亲转移。我们可以假设已经知道子树的DP值,此时当前点的DP值可以表示用父亲的DP值表示。把这个形式带入原式,就可以用自己表示子树。然后化简式子,可以得到一个新的转移。那么可以从下向上传递参数解决DP有环的问题。

  • 无限项等比数列的求和
    当公比q的绝对值小于$1$时
    $$
    \sum_{i}^{\inf} x^i = \frac{a_1}{1-q}
    $$

  • $\text{sizeof()}$函数的坑点
    如果一个函数中传了一个数组$a$,这个时候你$\text{memset(a,0,sizeof a)}$。
    看起来没有什么问题,其实只改了前面几个字节。
    因为传入的a是指针,$\text{sizeof(a)=8}$

  • FFT是循环卷积
    卷的时候会取膜,不清零会出事。
    $$F[i+j \% n]=\sum F[i]F[j]$$

  • 写指针的时候在结构体里面定义一定要初始化指针成NULL
    不然根据编译器版本可能是随机的。

  • low[x]>=dfn[v]割点,low[x]>dfn[v]

Leave a Reply

Your email address will not be published. Required fields are marked *