快速入门
首先,需要学习最值反演和二项式反演,式子如下:
\[ \max(S) = \sum_{T \subset S} (-1)^{|T| – 1} \min(T) \\ f_i = \sum_{j = 0}^i {i \choose j} g_j \Leftrightarrow g_i = \sum_{j = 0}^i (-1)^{i – j} {i \choose j} f_j \]
然后,你需要对反演和容斥有一定的理解,能理解容斥系数的意义。
首先,需要学习最值反演和二项式反演,式子如下:
\[ \max(S) = \sum_{T \subset S} (-1)^{|T| – 1} \min(T) \\ f_i = \sum_{j = 0}^i {i \choose j} g_j \Leftrightarrow g_i = \sum_{j = 0}^i (-1)^{i – j} {i \choose j} f_j \]
然后,你需要对反演和容斥有一定的理解,能理解容斥系数的意义。
记公式:
Or operation: arr[k + step] += opt * arr[k] And operation: arr[k] += opt * arr[k + step] Xor operation: A = arr[k], B = arr[k + step] arr[k] = A + B, arr[k + step] = A - B with inverse-operation, the inv2 is needed: arr[k] /= 2, arr[k + step] /= 2;