初赛知识点 | 洛灵酱的小窝

洛灵酱的小窝

闻道有先后,术业有专攻。

0%

初赛知识点

渐进时间复杂度

位运算

异或

相同为0,不同为1。

n0n^{\wedge}0不变,n1n^{\wedge}1取反。

补码

源码的绝对值取反加1。

运算顺序

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

排列组合

全排列

Anm=n×(n1)×(n2)××(nm+1)=n!(nm)!A^m_n=n \times (n-1) \times (n-2) \times \cdots \times (n-m+1) = \frac{n!}{(n-m)!}

全组合

Cnm=AnmAmm=n×(n1)×(n2)××(nm+1)1×2×3×4××m=n!m!(nm)!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[1n]A[1 \ldots n]如有i<ji \lt jA[i]>A[j]A[i] \gt A[j]则称为逆序对。

模运算

(a×b)modp=(amodp×bmodp)modp(a \times b) \bmod p = (a \bmod p \times b \bmod p) \bmod p

(a+b)modp=(amodp+bmodp)modp(a+b) \bmod p = (a \bmod p + b \bmod p) \bmod p

(ab)modp=(amodpbmodp)modp(a-b) \bmod p = (a \bmod p - b \bmod p) \bmod p

(abmodp)=((amodp)b)modp(a^b \bmod p) = ((a \bmod p) ^ b) \bmod p

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

((a+b)modp×c)modp=((a×c)modp+(b×c)modp)modp((a+b) \bmod p \times c) \bmod p = ((a \times c) \bmod p + (b \times c) \bmod p) \bmod p