Welcome to Liam's Blog

void _main() {
    int n;
    scanf("%d",&n);
    vec<int> p(n),s(n);
    for(auto &i : p) scanf("%d",&i),--i;
    reverse(p.begin(),p.end());
    for(int i=1; !p.empty(); ++i) {
        set<int> st;
        vec<bool> v(n,0);
        for(auto u : p) st.insert(u);
        for(auto u : p) {
            if(!v[u]) {
                v[u]=true;
                s[u]=i;
                auto it=st.find(u);
                if(it!=st.begin()) {
                    auto j=it;
                    --j;
                    v[*j]=true;
                }
                {
                    auto j=it;
                    ++j;
                    if(j!=st.end()) v[*j]=true;
                }
            }
            st.erase(u);
        }
        vec<int> q;
        for(auto u : p) if(!s[u]) q.push_back(u);
        p=q;
    }
    for(auto i : s) printf("%d ",i);
    putchar('\n');
}

补充

这个做法十分的不直观，因为考虑 $p = \{1,2,3,4\}$，若 $f = \{1,2,1,2\}$，虽然符合任意时刻相邻两个都不相同，但却是非法的。

这是因为当我们把 $\{1,3\}$ 两个位置的 $f$ 标为 $1$ 时，缩小了问题规模，删除了他们，这时 $p = \{2,4\}$，因此 $2$ 与 $4$ 相邻，我们就不能使 $f = \{2,2\}$，而是 $f = \{3,2\}$，合并得到 $f = \{1,3,1,2\}$。

2024年6月22日
分类于 Poly
需要 4 分钟阅读时间

FFT & NTT 复习笔记

默认文中的形如 $[l,r)$ 的区间为其与整数集的交集。

快速变换

设原多项式为 $F(x) = \sum_{i \in [0,n)} a_i x ^ i$，其中 $n = 2 ^ k, k \in \mathbb Z ^ +$。

我们要求 $\forall i \in [0,n),\hat a_i = F(t_i)$，其中 $t$ 是一个长度为 $n$ 且两两互不相同的序列。

显然 $F$ 可以被一组 $\hat a,t$ 唯一确定，即点值表示法。

另设两个多项式

\[ G_0(x)=a_0 + a_2 x + \dots + a_{n - 2} x^{\frac n 2 - 1} \\ G_1(x)=a_1 + a_3 x + \dots + a_{n - 1} x^{\frac n 2 - 1} \\ \]

则有

\[ \begin{aligned} F(x) & = \sum_{i \in [0,n)} a_i x ^ i \\ & = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-1} x^{n-1} \\ & = (a_0 + a_2 x^2 + \dots + a_{n-2} x^{n-2}) + (a_1 x + a_3 x^3 + \dots + a_{n-1} x^{n-1}) \\ & = G_0 (x ^ 2) + x G_1 (x ^ 2) \\ \end{aligned} \]

考虑构造单位根 $\omega _n ^k$ 满足 $\omega _n ^{\frac n 2} = -1, \omega _{2n} ^ {2k} = \omega _n ^k$。

显然也有 $\omega _n ^n = \omega _n ^0 = 1$。

设 $\forall i \in [0,n), t_i = \omega _n ^i$。

当 $x = \omega _n ^k, k \in [0,\frac n 2)$ 时显然有

\[ \begin{aligned} F(\omega _n ^k) & = G_0(\omega _n ^{2k}) + \omega _n ^k G_1(\omega _n ^{2k}) \\ & = G_0(\omega _ {\frac n 2} ^ k) + \omega _n ^k G_1(\omega _{\frac n 2} ^k) \\ \end{aligned} \]

当 $x = \omega _n ^{k + \frac n 2}, k \in [0,\frac n 2)$ 时有

\[ \begin{aligned} F(\omega _n ^{k + \frac n 2}) & = G_0(\omega _n ^{2k + n}) + \omega _n ^{k + \frac n 2} G_1(\omega _n ^{2k + n}) \\ & = G_0(\omega _n ^{2k} \cdot \omega _n ^n) - \omega _n ^k G_1(\omega _n ^{2k} \cdot \omega _n ^n) \\ & = G_0(\omega _n ^{2k}) - \omega _n ^k G_1(\omega _n ^{2k}) \\ & = G_0(\omega _{\frac n 2} ^k) - \omega _n ^k G_1(\omega _{\frac n 2} ^k) \\ \end{aligned} \]

由于两者只有一个符号的差异，于是 $F$ 的点值可以直接 $\mathrm O(n)$ 从 $G_0, G_1$ 的点值得到。

递归解决，时间复杂度 $\mathrm O(n \log n)$。

逆变换

设变换后的点值序列为 $\hat a$，即

\[ \begin{aligned} \forall i \in [0,n), \hat a_i & = F(\omega _n ^i) \\ & = \sum _{j \in [0,n)} a_j (\omega _n ^i)^j \\ & = \sum _{j \in [0,n)} a_j \omega _n ^{ij} \\ \end{aligned} \]

设多项式 $\hat F(x) = \sum _{i \in [0,n)} \hat a_i x^i$。

对 $\hat F$ 进行点值变换（$\forall i \in [0,n),t_i = \omega _n ^{-i}$），设点值序列为 $s$。

则有

\[ \begin{aligned} \forall i \in [0,n), s_i & = \hat F(\omega _n ^{-i}) \\ & = \sum _{j \in [0,n)} \hat a_j (\omega _n ^{-i}) ^j \\ & = \sum _{j \in [0,n)} \omega _n ^{-ij} \hat a_j \\ & = \sum _{j \in [0,n)} \omega _n ^{-ij} \sum _{k \in [0,n)} a_k \omega _n ^{jk} \\ & = \sum _{j \in [0,n), k \in [0,n)} \omega _n ^{-ij} a_k \omega _n ^{jk} \\ & = \sum _{j \in [0,n), k \in [0,n)} \omega _n ^{j(k-i)} a_k \\ & = \sum _{k \in [0,n)} a_k \sum _{j \in [0,n)} \omega _n ^{j(k-i)} \\ & = \sum _{k \in [0,n)} a_k \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j \\ \end{aligned} \]

显然第二个求和是一个等比数列，由等比数列求和公式 $\sum _{i \in [m,n)} p^i = \frac {p^m - p^n} {1 - p}$ 得：

当 $\omega _n ^{k-i} \not = 1 \iff i \not = k$

\[ \begin{aligned} \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j & = \frac {1 - \omega _n ^{(k-i) n}} {1 - \omega _n ^{k-i}} \\ & = \frac {1 - (\omega _n ^{k-i}) ^n} {1 - \omega _n ^{k-i}} \\ & = \frac {1 - 1} {1 - \omega _n ^{k-i}} \\ & = 0 \end{aligned} \]

当 $\omega _n ^{k-i} = 1 \iff i = k$

\[ \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j = \sum _{j \in [0,n)} 1 = n \]

因此

\[ \begin{aligned} \forall i \in [0,n), s_i & = \sum _{k \in [0,n)} a_k \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j \\ & = n a_i \\ \end{aligned} \]

于是我们有

\[ \forall i \in [0,n), a_i = \frac {s_i} n \]

构造单位根

FFT

在复数域下，有 $\omega _n = \cos \frac {2 \pi} n + \mathrm i \sin \frac {2 \pi} {n}$。

其中 $\mathrm i = \sqrt {-1}$ 是虚数单位，可以用 C++ 中的 complex 库中的 std::complex<double/long double> 存储复数。

NTT

对于模数 $P \in \mathbb P, \exists n,k \in \mathbb Z^+, P=2^nk+1$，在模 $P$ 意义下有 $\omega _n \equiv g ^ {\frac {P-1} n}$，其中 $g$ 是原根。

$g$ 是模 $P$ 意义下的原根当且仅当 $g ^i \not \equiv 1 \pmod P,\forall i \in [1,\phi(P))$ 且 $g ^{\phi(P)} \equiv 1 \pmod P$。

specially，$\forall P \in \mathbb P$，其原根 $g$ 满足 $\forall i \in [1,P-1), g ^i \not \equiv 1 \pmod P$ 且 $g^{P-1} \equiv 1 \pmod P$。

于是对 $n = 2 ^m, m \in \mathbb Z ^+$，我们有 $\omega _n ^n \equiv g ^{\frac {P - 1} {n} \cdot n} \equiv g ^{P - 1} \equiv 1, \pmod P$，且 $\omega _n ^{\frac n 2} \equiv g ^{\frac {P - 1} 2} \equiv \pm \sqrt {g ^ {P - 1}} \equiv \pm 1 \pmod P$，又 $g ^ {\frac {P-1} 2} \not \equiv 1 \pmod P$，所以 $\omega _n ^{\frac n 2} \equiv -1 \pmod P$。

还有 $\omega _{2n} ^{2k} \equiv g ^{\frac {2k(P-1)} {2n}} \equiv g ^{\frac{k(P-1)} n} \equiv \omega _n ^k \pmod P$

由于原根的特殊性，模数 $P \in \mathbb P$ 有特殊的限制，一般有 $P = k 2 ^m + 1, k,m\in \mathbb Z ^+$。

常见的模数有

\[ \begin{aligned} 167772161 = 5 \times 2 ^{25} + 1, g = 3 \\ 469762049 = 7 \times 2 ^{26} + 1, g = 3 \\ 754974721 = 45 \times 2 ^{24} + 1, g = 11 \\ 998244353 = 119 \times 2 ^{23} + 1, g = 3 \\ 1004535809 = 479 \times 2 ^{21} + 1, g = 3 \\ \end{aligned} \]

2024年6月16日
分类于 Geometry
需要 1 分钟阅读时间

平面直角坐标系的点绕原点旋转公式及证明

设点 $A(x,y)$ 绕原点 $O(0,0)$ 逆时针旋转 $\beta$，则设在极坐标系下 $A$ 的坐标为 $(r,\alpha)$

这意味着 $x=r \cos \alpha, y=r \sin \alpha$

目标点 $A'(x',y')$ 的极坐标即为 $(r,\alpha + \beta)$

展开（其中 $\sin$ 和 $\cos$ 的展开参考 here）：

\[ \begin{aligned} x' & = r \cos (\alpha + \beta) \\ & = r(\cos \alpha \cos \beta - \sin \alpha \sin \beta) \\ & = r\cos \alpha \cos \beta - r\sin \alpha \sin \beta \\ & = x \cos \beta - y \sin \beta \\ \end{aligned} \]

\[ \begin{aligned} y' & = r \sin (\alpha + \beta) \\ & = r (\sin \alpha \cos \beta + \cos \alpha \sin \beta) \\ & = r \sin \alpha \cos \beta + r\cos \alpha \sin \beta \\ & = y \cos \beta + x \sin \beta\\ \end{aligned} \]

结论：点 $(x,y)$ 绕原点逆时针旋转 $\theta$ 后坐标为 $(x \cos \theta - y \sin \theta, x \sin \theta + y \cos \theta)$。

2024年6月16日
分类于 Geometry
需要 1 分钟阅读时间

$\sin/\cos(\alpha+\beta)$ 的展开证明

图

\[ \begin{aligned} \cos(α+β) &= OB \\ & = OD - BD \\ & = OD - EC \\ & = OC \cos \beta - AC \sin \beta \\ & = OA \cos \alpha \cos \beta - OA \sin \alpha \sin \beta \\ & = \cos \alpha \cos \beta - \sin \alpha \sin \beta \end{aligned} \]

\[ \begin{aligned} \sin(α+β) &= AB \\ & = AE + BE \\ & = AE + CD \\ & = AC \cos \beta + OC \sin \beta \\ & = OA \sin \alpha \cos \beta + OA \cos \alpha \sin \beta \\ & = \sin \alpha \cos \beta + \cos \alpha \sin \beta \\ \end{aligned} \]

2024年4月30日
分类于 Poly
需要 5 分钟阅读时间

$\rm FWT$ (Fast Walsh Transform) 学习笔记

本文中使用 $\cap$ 表示按位与，用 $\cup$ 表示按位或

与/或卷积

问题引入

给定长度为 $2^n$ 的数列 $A,B$，求 $C_i = \sum_{j \cup k = i} A_j \times B_k$

显然有 $O(4^n)$ 的暴力

正变换

这一部分可以参考 FMT 中的 Zeta 变换，即定义 $\hat A_i$ 为序列 $A$ 中 $i$ 的子集和

快速变换

考虑分治

对于长度为 $2^n$ 的待求解的 $\hat A$，我们把它分成独立的两部分，即 $[0,2^{n-1})$ 和 $[2^{n-1},2^n)$ 两个区间分别求解

然后考虑这两个区间之间的贡献，发现只有 $[0,2^{n-1})$ 对 $[2^{n-1},2^n)$ 有贡献，于是对于 $i \in [0,2^{n-1})$，将 $\hat A_{i}$ 加到 $\hat A_{i+2^{n-1}}$ 中即可

时间复杂度 $O(n 2^n)$

逆变换

我们只需要对照正变换中的操作步骤，一步一步撤销变换即可

即对于 $i \in [0,2^{n-1})$，将 $\hat A_{i+2^{n-1}}$ 减去 $\hat A_{i}$ 的贡献，然后再递归地求解

当然还有另外的做法，即我们要将长度为 $2^n$ 的 $\hat A_i$ 在全集为 $2^n-1$ 的情况下（即不考虑目前的长度外的子集）只包括自己的 $A_i$，那么我们递归地求解完左右两个区间后，肯定有 $\forall i\in [0,2^{n-1}),\hat A_{i+2^{n-1}}=\hat A_i+A_{i+2^{n-1}}$，因此减去贡献即可

in brief，可以先递归再减贡献，这样逆变换与正变换只有一个 +/- 的变化

推广

对于 $\cap$ 的情况，与 $\cup$ 十分相似，请读者尽量自己构造变换，推一下式子，可以加深理解

如果没有思路，here

异或卷积

问题引入

给定长度为 $2^n$ 的数列 $A,B$，求 $C_i = \sum_{j \oplus k = i} A_j \times B_k$

原理

设 $\operatorname{popcnt}(i)$ 表示 $i$ 在二进制下 1 的个数，则有

\[ \operatorname{popcnt}(i \cap k) + \operatorname{popcnt}(j \cap k) \equiv \operatorname{popcnt}((i\oplus j)\cap k) \pmod 2 \]

证明：显然 $k$ 为 $0$ 的位上，$i,j$ 的取值不影响结果，那么设 $i'=i\cap k,j'=j\cap k$，那么问题转化为 $$ \operatorname{popcnt}(i') + \operatorname{popcnt}(j') \equiv \operatorname{popcnt}(i'\oplus j') \pmod 2 $$ 对于 $i',j'$ 每一位分开讨论，原命题易证

即异或不会改变 $1$ 的总数的奇偶性

正变换

我们尝试构造一个变换 $$ \hat A_i = \sum_j g(i,j) A_j $$ 例如对于 $\cup$ 卷积，$g(i,j)=[i\cup j=i]$

这个 $g$ 函数满足以下性质：

\[ \begin{aligned} & \because \hat C_i = \hat A_i \times \hat B_i \\ & \therefore \sum_{p} g(i,p)C_p = \sum_{j,k} g(i,j)\times g(i,k)\times A_j \times B_k \\ & \therefore \sum_{p} g(i,p) \sum_{j \oplus k = p} A_j \times B_k = \sum_{j,k} g(i,j)\times g(i,k)\times A_j \times B_k \\ & \therefore \sum_{j,k} g(i,j \oplus k) A_j \times B_k = \sum_{j,k} g(i,j)\times g(i,k)\times A_j \times B_k \end{aligned} \]

即我们要使得 $g(i,j)\times g(i,k) = g(i,j \oplus k)$

因为 $\operatorname{popcnt}(i \cap k) + \operatorname{popcnt}(j \cap k) \equiv \operatorname{popcnt}((i\oplus j)\cap k) \pmod 2$，我们发现 $g(i,j) = (-1)^{\operatorname{popcnt}(i \cap j)}$ 满足这个性质

\[ \hat A_i = \sum_j (-1)^{\operatorname{popcnt}(i \cap j)} A_j \]

手动推一下式子：

\[ \begin{aligned} \hat A_i \times \hat B_i & = \sum_j g(i,j)A_j \times \sum_k g(i,k) B_k\\ & = \sum_j (-1)^{\operatorname{popcnt}(i \cap j)} A_j \times \sum_k (-1)^{\operatorname{popcnt}(i \cap k)} B_k\\ & = \sum_{j,k} (-1)^{\operatorname{popcnt}(i \cap j) + \operatorname{popcnt}(i \cap k)} A_j \times B_k \\ & = \sum_{j,k} (-1)^{\operatorname{popcnt}(i \cap (j \oplus k))} C_{j \oplus k} \\ & = \sum_{p} (-1)^{\operatorname{popcnt}(i \cap p)} C_p \\ & = \sum_p g(i,p) C_p \\ & = \hat C_i \end{aligned} \]

快速变换

有点抽象，画个 $n=3$ 的图来模拟一下

快速变换图解

假设现在我们要考虑从 $n=2$ 到 $n=3$ 的变换，我们发现左边是 0??，右边是 1??，分别多出一个最高位

设原变换为 $F_i$ ，目标变换为 $G_i$

左 $\to$ 左

我们发现左边内部之间的 $\cap$ 结果不变，因此 $\forall i<4, G_i \gets F_i$

左 $\to$ 右 / 右 $\to$ 左

我们发现 0?? $\cap$ 1?? = 0??，因此其 1 的个数不变，因此 $\forall i<4,G_i \gets F_{i+4}, G_{i+4} \gets F_i$。

右 $\to$ 右

我们发现之前是 ?? $\cap$ ?? = ??，但是现在在前面加了一个 1，因此 $-1$ 的指数加一，所以 $\forall i<4,G_{i+4} \gets -F_{i+4}$

综上，我们有 $\forall i<4,G_i=F_i+F_{i+4}, G_{i+4}=F_i-F_{i+4}$

generally，对于从 $n-1$ 到 $n$ 的变换，我们有

\[ \forall i<2^{n-1}, G_i=F_i+F_{i+2^{n-1}}, G_{i+2^{n-1}}=F_i-F_{i+2^{n-1}} \]

时间复杂度 $O(n2^n)$。

逆变换

对照上面式子易得 ~~（留给读者思考）~~

模板题

核心代码如下

void fwtOr(ll *a,int n,int type) {
    for(int i=1; i<(1<<n); i<<=1)
        for(int j=0; j<(1<<n); j+=(i<<1))
            for(int k=0; k<i; ++k)
                (a[j+k+i]+=type*a[j+k])%=P;
}
void fwtAnd(ll *a,int n,int type) {
    for(int i=1; i<(1<<n); i<<=1)
        for(int j=0; j<(1<<n); j+=(i<<1))
            for(int k=0; k<i; ++k)
                (a[j+k]+=type*a[j+k+i])%=P;
}
void fwtXor(ll *a,int n,int type) {
    for(int i=1; i<(1<<n); i<<=1)
        for(int j=0; j<(1<<n); j+=(i<<1))
            for(int k=0; k<i; ++k) {
                ll u=a[j+k],v=a[j+k+i];
                a[j+k]=(u+v)%P;
                a[j+k+i]=(u-v)%P;
                if(type==-1) {
                    (a[j+k]*=Pi2)%=P;
                    (a[j+k+i]*=Pi2)%=P;
                }
            }
}

进阶理解

$\rm FWT$ 的变换本质实际上是构造 $g$ 的过程。

设 $\hat A_i = \sum_j g(i,j) A_j$，那么这个 $n \times n$ 的 $\lceil$转移矩阵$\rfloor$ 被称为位矩阵。

对于不同的卷积形式，我们需要构造不同的位矩阵。

特别注意由于我们需要逆变换，因此矩阵必须有逆。

形式化地，对于 $\odot$ 卷积，即 $C_i = \sum_{j \odot k = i} A_j B_k$，我们需要构造如下位矩阵：

\[ \begin{aligned} & \hat C_i = \hat A_i \hat B_i \\ \iff & \sum_j g(i,j) C_j = \sum_j g(i,j) A_j \sum_k g(i,k) B_k \\ \iff & \sum_j g(i,j) C_j = \sum_j \sum_k g(i,j) g(i,k) A_j B_k \\ \iff & g(i,j \odot k) = g(i,j) g(i,k) \end{aligned} \]

写的不是很严谨，请读者自己手推一下。

对于上文的三类卷积，其位矩阵的构造显然为

\[ g_{\cup}(i,j) = [i \cup j = i] \\ g_{\cap}(i,j) = [i \cap j = i] \\ g_{\oplus}(i,j) = (-1)^{\mathrm{popcnt} (i \cap j)} \]

$\rm FWT$ 的线性性

设 $\mathrm{FWT}(A)_i = \hat A_i = \sum_j g(i,j) A_j$，则有如下引理。

$\mathrm{FWT}(A+B) = \mathrm{FWT}(A) + \mathrm{FWT}(B)$

根据公式显然。

$\mathrm{FWT}(cA) = c\mathrm{FWT}(A)$

这个也是显然（

$\mathrm{FWT}(A^{-1})_i = g(i,0) \mathrm{FWT}(A)_i^{-1}$

\[ \begin{aligned} & \mathrm{FWT}(A^{-1})_i \mathrm{FWT}(A)_i \\ & = \sum_j g(i,j) A^{-1}_j \sum_k g(i,k) A_k \\ & = \sum_j \sum_k g(i,j \odot k) A^{-1}_j A_k \\ & = \sum_{p} g(i,p) \sum_{j \odot k = p} A^{-1}_j A_k \\ & = \sum_{p} g(i,p) [p=0] \\ & = g(i,0) \\ \end{aligned} \]

2024年4月24日
分类于 Poly
需要 3 分钟阅读时间

FMT(Fast Möbius Transform) 学习笔记

小 Tips：在计算机语言中 $\cap$ = & / and， $\cup$ = | / or

定义

定义长度为 $2^n$ 的序列的 and 卷积 $A = B * C$ 为 $A_i=\sum_{j \cap k = i}{B_j \times C_k}$

考虑快速计算

Zeta 变换

定义长度为 $2^n$ 的序列的 Zeta 变换 为

\[ \hat A_i = \sum_{j \subseteq i}{A_j} \]

即子集和

它具有一下性质：

\[ \hat B_i \times \hat C_i = \sum_{j \subseteq i} B_j \times \sum_{k \subseteq i} C_k = \sum_{p \subseteq i} \sum_{j \cap k = p} B_j \times C_k = \sum_{p \subseteq i} A_p = \hat A_i \]

相当于 FFT 中的点值表示法，用以加速卷积过程

快速变换

暴力求解 $\hat A$ 最优时间复杂度为 $3^n$，考虑加速

考虑 子集DP ，有一篇很好的博客¹，这里大概讲解一下。

其实 $\hat A$ 本质上是一个高维（$n$ 维）前缀和

如果我们要求二维前缀和，显然可以通过一下代码实现：

// 1st
for(int i=1; i<=n; ++i)
    for(int j=1; j<=m; ++j)
            a[i][j]+=a[i-1][j];
// 2nd
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
            a[i][j]+=a[i][j-1];

我们发现 1st 完成后 a[i][j] 表示的是 $\sum_{k \le i} a_{k,j}$，即 $(i,j)$ 上方的元素和

那么 2nd 便是将 $(i,j)$ 左边操作后的 $\sum_{k \le j} a_{i,k}$ 累加到 a[i][j] 中，即完成二维前缀和

下面拓展到三维前缀和

// 1st
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
        for(int k=1; k<=n; ++k)
            a[i][j][k]+=a[i-1][j][k];
// 2nd
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
        for(int k=1; k<=n; ++k)
            a[i][j][k]+=a[i][j-1][k];
// 3rd
for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
        for(int k=1; k<=n; ++k)
            a[i][j][k]+=a[i][j][k-1];

类似地，1st,2nd 中处理除了第 k 平面中的二维前缀和，3rd 在立体空间中把他们加起来，成为三维前缀和

回到 Zeta 变换：

\[ \hat A_i = \sum_{j \subseteq i}{A_j} \]

如果我们用二进制 $(x_{n-1}x_{n-2}x_{n-3}\ ...\ x_2x_1x_0)_2$ 表示集合 $i$，二进制 $(y_{n-1}y_{n-2}y_{n-3}\ ...\ y_2y_1y_0)_2$ 表示集合 $j$

那么 $\hat A_i$ 可以被视为 $n$ 维前缀和，即 $$ \hat A_i = \sum_{y_{n-1}\le x_{n-1},y_{n-2}\le x_{n-2}, ..., y_1\le x_1,y_0\le x_0} A_j $$

当然，下标都为 0/1

因此，我们有如下 Code：

for(int i=0; i<n; ++i)
    for(int j=0; j<(1<<n); ++j)
        if(j&(1<<i))
            a[j]+=a[j^(1<<i)];

以上 Code 的 naive 形式为：

for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i1>0) a[i1][i2][...][in]+=a[i1-1][i2][...][in];
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i2>0) a[i1][i2][...][in]+=a[i1][i2-2][...][in];
...
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(in>0) a[i1][i2][...][in]+=a[i1][i2][...][in-1];

~~不要质疑我代码编译不通过~~

因此，我们用 $O(n2^n)$ 的时间复杂度解决了 Zeta 变换

逆变换

warning：此处不是 莫比乌斯反演！

众所周知，前缀和的逆运算即为差分

我们发现，只需要先将最后一维差分，即可将序列处理为 $n-1$ 维前缀和

即

for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(in>0) a[i1][i2][...][in]-=a[i1][i2][...][in-1];
...
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i2>0) a[i1][i2][...][in]-=a[i1][i2-2][...][in];
for(int i1=0; i1<2; ++i1) for(int i2=0; i2<2; ++i2) ... for(int in=0; in<2; ++in) if(i1>0) a[i1][i2][...][in]-=a[i1-1][i2][...][in];

但实际上因为前缀和都是无序的，因此我们直接正着做就可以啦

只需要把正变换的 += 改为 -= 就可以了

扩展

有时候，题目给的不是 $\cap$ ，而是 $\cup$ 怎么办？

那我们重定义 Zeta 变换 为： $$ \hat A_i = \sum_{i \supseteq j} A_j $$ 再推一下式子： $$ \hat B_i \times \hat C_i =\sum_{i\supseteq j} B_j \times \sum_{i\supseteq k} C_k =\sum_{i\supseteq j,i\supseteq k} B_j \times C_k =\sum_{i\supseteq p} \sum_{j \cup k=p} B_j \times C_k =\sum_{i\supseteq p} A_p =\hat A_i $$ 变换即超集和，高维后缀和

求法也很简单，只用将源代码中的 if(j&(1<<i)) 该为 if(!(j&(1<<i))) 即可

是 $\oplus$ 怎么办？

~~快去学 FWT 吧~~

例题

ABC349F

再送你一个并/交集的小口诀：下并或，上交与

高维前缀和总结(sosdp) - heyuhhh - 博客园 (cnblogs.com) ↩↩

2024年4月21日
分类于 Record
需要 2 分钟阅读时间

AtCoder 训练记录

~~先贴上本人主页~~

ABC347

$\Delta=\color{red}{-24}$

~~蓝名保卫战，极限 1600~~

C 题还是有些思维难度的，最后才做出来，但是不够简洁

E 题忘开 %lld 喜提罚时

D 题最难评，又 WA 又 RE，最后如果输出不符合条件就输出 -1 才过

F 题原题，但是不会（

赛后发现就是一个二维前缀和 + 二位前缀max，还是挺简单的

~~G 题不会~~

赛时打的太急了，罚时太多，速度也被拖慢了，同分的最高 performance 有 2000+，还是代码实现不够快和准

AGC066

$\Delta=\color{red}{-21}$

~~E 题原题，还抓了一个抄题解的~~

A 题还是挺水的，只是没想到从奇偶性的角度来想，题解给的是 $O(N ^ 2 D)$ 的做法，但是有更优且更简单的做法 $O(N ^ 2)$，但是没想到，还是考思维。

B 题有点愚人节，python 语言优势很大（自带高精度），用几个 $5 ^ x$ 拼起来多随机几次就完了，难绷（

~~蓝名没了 /ll~~

ABC348

$\Delta=\color{green}{114}$

performance 2300+ 祭

0罚时切 A ~ F，~~让我又想起了那场似的 rating~~

F 题听说比较水，暴力 + O3 可过，但是我用 bitset $O(\frac{N ^ 2 M}{\omega})$ 也过了（

G 题决策单调性优化板题，原题两道：here & here ~~（但我不会）~~

upd on 2024.4.14 : G 题改出来了，应用单调性还是比较简单的，但是难在证明

ABC349

$\Delta=\color{green}{67}$

A ~ D 都比较顺畅，D 题盲猜 $\text{lowbit}$ 喜提机房一血，E 题没开 long long 喜提一发罚时与机房一血

然后就坐着与 F & G 干瞪眼，F 先是用 cdq 尝试水分，后来将不是 $M$ 因数的删掉了，还是不行

最后发现 $M$ 最多有 $13$ 个因数，直接 $O(2^{13}N) \approx 1.638 \times 10^9$ 过了，~~AtCoder 神机~~

但是打得太急，F 题 7 发罚时，最后 4 发最离谱，一发没取模，一发取模太慢 TLE，一发将取模改成减法写错了，最后一发两处取模是 copy 的都错了，漏了一处没改（

$\color{green}{525} \color{red}{(7)}$ ！！

G 题直接并查集开水，快 T 了就 No，过了一半的数据点

实际上还可以开随机化，因为对于 $\forall i$，有些连边是不需要的，有概率连到与目标解答案相同的状态，但比赛后才想到（

ABC350

$\Delta=\color{red}{-6}$

之前的总结写的太笼统了，更像是提要。刚好今天实在是打 emo 了，犯了很多离谱的错误，想写一篇个人直观的反思，从 rating 和 performance 中跳出来，慢慢地审视整个过程。

A 题其实没有问题，可以直接A的，但是把 %03d 写成了 %02d 样例中也没有 ABC001，于是就挂了。

后来几道题一直很慌，越慌，越是想打快。越是快，就越出错。这很严重拖慢了整个切题的速度。C 题本来是没什么问题的，但是急着想过掉它，核心的代码几乎一半是错的，第一发直接罚时，这时心情也是很差了，很焦躁。后来逼迫自己冷静下来，又在草稿纸上画了几下，思路便逐渐清晰，于是便改对了。

到了赛点的后三题后，我其实刚刚松一口气，看到 E 题又自闭了，毕竟概率题上次就栽过，是ABC342F，这次又看到，心里一紧，只好先尝试 F 题。

F 题读完题后没多久就想到了 dfs，然而实现中还是有一些小错误，如 for 循环里更新 i 的话，它实际上还会 ++i/--i 一次，会跳过一个位置。好在没罚时。

切完 F 题后看了一下 G 题，一开始读错题了以为那个在线是假的，高高兴兴拿样例试水发现是错的。没办法，于是看 E 题，结果旁边的人 ~~看我蓝名快没了~~ 好心旁敲侧击，于是想到 DP，中途还有一个自己转移到自己的，想到了之前的一道题目 ~~虽然我没改出来~~ ，于是移项解方程即可。

一开始 $10^{18}$ 我认为计搜是过不了的，因此打得不够坚定，还有一个变量重名调了很久，实现不够稳和准。开始是想着拿去水分的，但是直接过了，而且时间也很充裕（7ms）。赛后看题解，计搜时间复杂度实际上是 $O(\log^3 n)$，但是主要问题是不会证明，对自己没有信心，于是犹豫了很久。

到了最后的 G 题，此时还剩下 20 分钟，已经机房内有人切了 G 题。出于对 G 题的潜意识压力以及前面比赛的表现，我此时已经基本失去思考能力了，脑子一片嗡嗡的根本想不到正解，打了一个根本就没概率的随机化过了一半，最后遗憾收场。

机房内同年级的有 4 个人过了 G 题，其中 3 人都是水过的，还包括两个代码相似的人。第四个大佬用了 splay。

到这里，你可能认为 G 题还是有点难度的。但是，实际上，这也是我在比赛中犯的最后一个，也是最大的一个错误。

读完 G 题，其实不难想到如果维护好了森林中的每棵树有确定的根（具体是哪个节点与答案无关），并且维护好了每个点在其所在连通块中的朝向这个根的父亲，那么求解答案是 $O(1)$ 的。比赛时这个念头在我脑海里一闪而过，但是很快就被否决了——原因很简单，这个维护过程直观上看是非常不可行的。后来，我转而去想 bitset 时间换空间，但一无所获。

然而，这就是问题所在——用暴力维护这些信息实际上的时间复杂度是正确的！因为每次连边的两个点都是在不同的连通块中，做完这次操作以后它们就会被合并，因此如果我们遍历一遍较小的连通块，总时间复杂度是 $O(n\log n)$！因此，这道 G 题出乎意料地短，甚至比我的随机化代码还要少。

写在最后：这次 ABC 可以看到除了少部分人，大多数人都没有取得很理想，甚至可以说糟糕的成绩。比赛结束后，我听到有人在机房里咒骂自己、题目和出题人的。还有人为了 rating 而闷闷不乐，诸如此类。但是有一点他们都错了，我们打比赛不是为了 rating 去打，不是为了成绩去打。以我为例，这次比赛我的 delta 是 -6，相对于之前 2200+ 的 performance，可谓是相当的差。但是，在这背后，是我被打乱的做题节奏，被扰乱的心态，是我过于激动的心情。这次比赛，暴露了我很多问题：代码实现不准不细心，读题不仔细，对时间复杂度的不敏感，对时间复杂度证明的不熟练，而这些，都为我提供了宝贵的经验，这远远不是几点 rating 所能给我的。之前还看到旁边的人比赛时一起讨论题目，其实也是十分不应该——如果人人都只在乎 rating 以至于无人在乎算法背后的玄妙，在乎它们的出处与归宿，那么 rating 早已失去它本来的意义了。希望各位在天涯海角的 OIer 都能保住自己的初心，守住心中的一寸净土，为了 OI，ACM，乃至 CS 的明天而砥砺前行。