『学习笔记』中国剩余定理
# 中国剩余定理(CRT)
中国剩余定理是用来解决如下问题的：
{x≡a1 (modm1)x≡a2 (modm2)... x≡an (modmn)\begin{cases}
x\equiv a_1\ \pmod{m_1}&\\
x\equiv a_2\ \pmod{m_2}&\\
...\ &\\
x\equiv a_n\ \pmod{m_n}
\end{cases}
⎩⎨⎧x≡a1 (modm1)x≡a2 (modm2)... x≡an (modmn)
注意：模数必须互质。
#...
more...
群论
# 置换
定义
有限集合到自身的双射（即一一对应）称为置换。集合 S={a1,a2,⋯ ,an}S = \left\{a_1, a_2, \cdots ,a_n \right\}S={a1,a2,⋯,an} 的置换可以表示为：
f=(a1,a2,⋯ ,anap1,ap2,⋯ ,apn)f = \begin{pmatrix}a_1, a_2, \cdots , a_n\\ a_{p_1}, a_{p_2}, \cdots ,a_{p_n}\end{pmatrix}
f=(a1,a2,⋯,anap1,ap2,⋯,apn)
p1,p2,⋯ ,pnp_1, p_2,...
more...
二维数点问题
# 二维数点
顾名思义，就是在一个二维平面内数一个矩形内有多少个点。
例题：P2163 [SHOI2007]园丁的烦恼
# 树状数组
根据二维前缀和的算法，把矩形和改成求 4 个坐标 (x,y)(x,y)(x,y) 到原点的矩形和，再容斥计算答案。
首先对坐标离散化，按 xxx 轴排序，从左到右依次插入每个点。对 yyy 轴维护一个树状数组。
插入：在相应的 yyy 轴坐标上加 1.
查询：由于按 xxx 轴从小到大插入的，树状数组内的点都在当前的 xxx 左边。所以查询小于当前 yyy 的和就是 (0,0)(0, 0)(0,0) 到 (x,y)(x, y)(x,y)...
more...
20220722
# A. 数正方体
推了 2.5h 没有推出来，心态非常崩。
主要是没有网通项式方面去想，考场上推出来递推式之后一直在优化递推……
通过手模不难发现，fi,j=fi−1,j−1+2×fi−1,jf_{i, j} = f_{i - 1, j - 1} + 2 \times f_{i - 1, j}fi,j=fi−1,j−1+2×fi−1,j.
然后再打一个更大的表，不难发现
fn,m=2n−m(nm)f_{n, m} = 2^{n - m} \dbinom {n}{m}
fn,m=2n−m(mn)
然后 O(n)O(n)O(n) 预处理，O(1)O(1)O(1)...
more...
