初赛知识点

• • 渐进时间复杂度
  • 位运算
    • 异或
    • 补码
  • 运算顺序
  • 排列组合
    • 全排列
    • 全组合
  • 逆序对
  • 模运算

渐进时间复杂度

位运算

异或

相同为0，不同为1。

$n^{\wedge}0$不变，$n^{\wedge}1$取反。

补码

源码的绝对值取反加1。

运算顺序

赋值运算符 < 逻辑运算符 < 关系运算符 < 算数运算符

排列组合

全排列

$A^m_n=n \times (n-1) \times (n-2) \times \cdots \times (n-m+1) = \frac{n!}{(n-m)!}$

全组合

$C^m_n= \frac{A^m_n}{A^m_m} = \frac{n \times (n-1) \times (n-2) \times \cdots \times (n-m+1)}{1 \times 2 \times 3 \times 4 \times \cdots \times m} = \frac{n!}{m!(n-m)!}$

逆序对

$A[1 \ldots n]$如有$i \lt j$且$A[i] \gt A[j]$则称为逆序对。

模运算

$(a \times b) \bmod p = (a \bmod p \times b \bmod p) \bmod p$

$(a+b) \bmod p = (a \bmod p + b \bmod p) \bmod p$

$(a-b) \bmod p = (a \bmod p - b \bmod p) \bmod p$

$(a^b \bmod p) = ((a \bmod p) ^ b) \bmod p$

$((a+b) \bmod p + c) \bmod p = (a + (b+c) \bmod p) \bmod p$

$((a+b) \bmod p \times c) \bmod p = ((a \times c) \bmod p + (b \times c) \bmod p) \bmod p$