xixike

# 中国剩余定理 (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​)​​ 注意：模数必须互质。 #...

# 置换 定义 有限集合到自身的双射（即一一对应）称为置换。集合 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​,⋯,an​ap1​​,ap2​​,⋯,apn​​​) p1,p2,⋯ ,pnp_1, p_2,...

# 二维数点 顾名思义，就是在一个二维平面内数一个矩形内有多少个点。 例题：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)...

# 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)...

# 二项式反演 # 公式 fn=∑i=0n(ni)gi⇔gn=∑i=0n(−1)n−i(ni)fif_n = \sum_{i = 0}^n \dbinom {n}{i}g_i \Leftrightarrow g_n = \sum_{i = 0}^n (-1)^{n - i} \dbinom ni f_i fn​=i=0∑n​(in​)gi​⇔gn​=i=0∑n​(−1)n−i(in​)fi​ 证明就不细说了。那么二项式反演的式子有什么用呢？ 恰好和至多的转换： 设 fkf_kfk​ 为恰好 kkk 个的方案数，gkg_kgk​ 为至多 kkk 个的方案数（恰好 kkk 个和至多 kkk...