NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【复习笔记】Week 5 冬令营准备

posted on 2019-12-06 19:36:03 | under 复习笔记 |

绪言

我知道 THW 和 PKW 的申请不容易通过。不过,既然大家都已经为我付出了这么多,假如真的有机会参加冬令营,我绝不能浪费如此沉重的机会。仅仅 10 天,我究竟能做到什么?我真的能在不放弃文化课的同时,把自己提升到省选水平吗?我不知道,但我必须前进。

希望与绝望并存,梦想与现实抗争。

最美的愿望 一定最疯狂
我就是我自己的神
在我活的地方

我和我最后的倔强
握紧双手绝对不放
下一站是不是天堂
就算失望 不能绝望

我和我骄傲的倔强
我在风中大声地唱
这一次为自己疯狂
就这一次 我和我的倔强

DAY 1

网络最大流

残量网络:一系列反边,其存在对原图没有任何影响,但可以利用类似 独木桥 的思路,使得流量能够反悔。

EK

思路: 每次通过 bfs 找到一条增广路,然后对增广路上的边维护残量网络。

复杂度: $O(n\cdot m^2)$

inline bool bfs() {
    memset(vis, 0, sizeof(vis));
    while (!q.empty())
        q.pop();
    // 每次清空信息
    flow[s] = 0x7fffffff;
    vis[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (register int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w;
            if (vis[v] || w <= 0)
                continue;
            vis[v] = true;
            flow[v] = min(flow[u], w);
            fa[v] = u;
            path[v] = i;
            // 记录增广路
            if (v == t)
                return true;
            q.push(v);
        }
    }
    return false;
}

inline void EK() {
    while (bfs()) {
        for (register int u = t; u != s; u = fa[u]) {
            edge[path[u]].w -= flow[t];
            edge[path[u] ^ 1].w += flow[t];
        }
        // 维护残量网络
        maxflow += flow[t];
    }
    return ;
}

Dinic

思路: 利用 bfs 获得一个增广图(包含当前状态下经过节点数最少的所有增广路),然后在搜索图上进行 dfs 增广,利用递归维护残量网络。

复杂度: $O(n^2\cdot m)$

可以看出 Dinic 在稠密图上的性能优于 EK 算法。

弧优化

思路: 由于在同一个增广图中,一条边被 dfs 之后就无法继续增广(因为经过该点的所有增广路容量已经流满),因此可以不再考虑这条边。

inline bool bfs() {
    memset(dep, 0, sizeof(dep));
    memcpy(cur, head, sizeof(cur));
    // 记得每次 bfs 都需要初始化
    dep[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w;
            if (dep[v] || w <= 0)
                continue;
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
    return dep[t];
}
// bfs 用于生成增广图

int dfs(int u, int flow) {
    if (u == t)
        return flow;
    int used = 0;
    // used 保存从增广图上的 u 出发能够获得的增广流量
    for (int i = cur[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        cur[u] = i;
        // 弧优化
        if (dep[v] == dep[u] + 1 && w > 0) {
            int inc = dfs(v, min(flow, w));
            // inc 表示经过 <u, v> 可以获得的增广流量
            if (inc > 0) {
                edge[i].w -= inc;
                edge[i ^ 1].w += inc;
                // 维护残量网络
                used += inc;
                flow -= inc;
                if (!flow)
                    return used;
                // flow 全部流满,则直接 return
            }
        }
    }
    return used;
}

inline void dinic() {
    while (bfs())
        maxflow += dfs(s, 0x7fffffff);
    return ;
}

ISAP 优化

思路: 分析 Dinic 算法的过程,可以发现每次 bfs 分层以生成增广图的本质是 放宽增广路所经过点数的限制。也就是说,Dinic 算法中获得的增广路所经过的点数是递增的。因此考虑如何不重新分层而实现放宽限制:只用从汇点 $t$开始反向 bfs 分层,获得每个点的深度,每次对一个点 $u$进行 dfs 增广以后,就执行 dep[u]++,从而达到了 Dinic 中重新分层而想要达到的目的。同时,gap[] 优化掉了无意义的增广尝试。

一些细节:

  1. ISAP 中 dfs() 函数的前一半和 Dinic 是一摸一样的,而且 ISAP 也可以进行弧优化;
  2. 还需要记录 gap[i] 表示深度为 i 的点的个数。如果图中某 gap[i] == 0,也就是说增广图出现了断层,则一定无法继续增广,直接结束程序;
  3. 由于 dep[t] = 1,因此执行 dfs(s, 0x7fffffff) 的条件是 dep[s] <= n
  4. 由于是反向分层,因此 dfs 路径上的点一定满足深度连续递减,而非连续递增。
inline void bfs() {
    dep[t] = 1;
    gap[1] = 1;
    q.push(t);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (register int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (dep[v])
                continue;
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
            // 维护 gap[]
            q.push(v);
        }
    }
    return ;
}

int dfs(int u, int flow) {
    if (u == t)
        return flow;
    int used = 0;
    for (register int i = cur[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        cur[u] = i;
        if (dep[u] == dep[v] + 1 && w > 0) {
            int inc = dfs(v, min(flow, w));
            if (inc > 0) {
                edge[i].w -= inc;
                edge[i ^ 1].w += inc;
                used += inc;
                flow -= inc;
                if (!flow)
                    return used;
            }
        }
    }
    // 与 Dinic (弧优化)一摸一样
    gap[dep[u]]--;
    if (!gap[dep[u]])
        dep[s] = n + 1;
    // 等价于结束 ISAP() 函数
    dep[u]++;
    gap[dep[u]]++;
    // 升层操作
    return used;
}

inline void ISAP() {
    bfs();
    while (dep[s] <= n) {
        memcpy(cur, head, sizeof(cur));
        maxflow += dfs(s, 0x7fffffff);
    }
    return ;
}

HLPP(究极最大流算法)

思路: 往 $s$处疯狂灌水,只要不超过容量就推流,然后入队进行 bfs,最后 $t$处的余流就是网络最大流。

这样朴素的想法正确性显然,不过由于残量网络的存在,会出现两个点相互推流从而陷入死循环的尴尬局面。为了防止这种情况,可以引入一个高度 $h[u]$,规定推流时只能由高处推向低处。特殊地, $h[s]=n$, $h[t]=0$且固定不变。若一个点推流后还有余流,则将其高度改为与其相邻的最低点高度 $+1$,然后入队;若没有余流,则什么也不做。很明显,如果一个点无法向 $t$推流,则其余流最终会经过残量网络还给 $s$。

但是即使做了高度优化,预推流算法依然很慢。此时需要再引入 gap[] 优化、优先队列优化。设 $h[t]=0$,先从 $t$开始 bfs,给每个点一个初始高度,并且规定只能在高度差为 $1$的点之间推流,然后执行下面的步骤:

  1. s 开始向外推流,将有余流的点放入优先队列;
  2. 不断从优先队列里取出最高的点 u 进行推流;
  3. u 还有余流,更新 h[u],放入优先队列;若高度出现断层,则直接把所有高于 u 的点的高度设为 n + 1(也就是 gap[] 优化)。

当出现断层时,高度更高的点永远无法再被推流,需要把余流推回 $s$,所以 gap[] 优化保证了不会出现无意义的推流;而优先队列优化保证了每次都是取出最高的节点进行推流,使得高度更新次数尽量减少。

复杂度: $O(n^2\sqrt m)$,但常数较大。

struct cmp {
    bool operator () (const int &lhs, const int &rhs) const {
        return h[lhs] < h[rhs];
    }
};
queue<int> q;
priority_queue<int, vector<int>, cmp> pq;

inline void bfs() {
    memset(h, 0x3f, sizeof(h));
    // 需要初始化为 0x3f3f3f3f 以排除不连通的点
    h[t] = 0;
    q.push(t);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (h[v] != 0x3f3f3f3f)
                continue;
            h[v] = h[u] + 1;
            q.push(v);
        }
    }
    return ;
} // 初始化高度

inline void push(int u) { // 推流函数
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && h[u] == h[v] + 1) {
            // 满足推流条件
            int flow = min(w, tmp[u]);
            // 计算可推流
            edge[i].w -= flow;
            edge[i ^ 1].w += flow;
            tmp[u] -= flow;
            tmp[v] += flow;
            // 推流,并且维护残量网络
            if (v != s && v != t && !vis[v]) {
                // 注意 s 和 t 不能入队
                vis[v] = true;
                pq.push(v);
            }
            if (!tmp[u])
                break;
            // 余流为 0,跳出循环
        }
    }
    return ;
}

inline void relable(int u) {
    h[u] = 0x3f3f3f3f;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0 && h[v] + 1 < h[u])
            h[u] = h[v] + 1;
        // 寻找相邻最低点,并更新自己的高度
    }
    return ;
}

int HLPP() {
    bfs();
    if (h[s] == 0x3f3f3f3f3f)
        return 0;
    // 连通性判无解
    h[s] = n;
    for (int i = 1; i <= n; i++)
        if (h[i] != 0x3f3f3f3f)
            gap[h[i]]++;
    // gap[] 统计
    for (int i = head[s]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (w > 0) {
            edge[i].w -= w;
            edge[i ^ 1].w += w;
            tmp[s] -= w;
            tmp[v] += w;
            if (v != s && v != t && !vis[v]) {
                vis[v] = true;
                pq.push(v);
            }
        }
    }
    // 预处理与 s 相邻的点
    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();
        vis[u] = false;
        // 一定记得出队清空 vis[]
        push(u);
        if (tmp[u]) { // 还有余流
            gap[h[u]]--;
            if (!gap[h[u]]) {
                for (int i = 1; i <= n; i++)
                    if (h[i] > h[u] && h[i] < n + 1)
                        h[i] = n + 1;
            } // gap[] 优化
            relable(u);
            gap[h[u]]++;
            vis[u] = true;
            pq.push(u);
        }
        // 没有余流则什么也不做
    }
    return tmp[t];
}

最小费用最大流

MCMF

思路: 顾名思义 就相当于把 bfs 替换为 SPFA 的 EK 算法。其中的 dis[] 即是最小单位费用。尝试经过 $<u,v>$ 增广的条件为:

  1. w > 0(满足最大流);
  2. dis[u] + c < dis[v](满足最小费用)。

剩余的部分和 EK 算法没有区别。

bool SPFA() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0, flow[s] = 0x7fffffff;
    vis[s] = true;
    fa[t] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        // SPFA 总是容易忘记这一步
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w, c = edge[i].c;
            if (w > 0 && dis[u] + c < dis[v]) {
                // 尝试增广的两个条件
                flow[v] = min(flow[u], w);
                dis[v] = dis[u] + c;
                fa[v] = u;
                path[v] = i;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                    // SPFA 中的入队
                }
            }
        }
    }
    return fa[t];
}

inline void MCMF() {
    while (SPFA()) {
        for (register int u = t; u != s; u = fa[u]) {
            edge[path[u]].w -= flow[t];
            edge[path[u] ^ 1].w += flow[t];
        }
        maxflow += flow[t];
        mincost += flow[t] * dis[t];
        // 记得统计 mincost
    }
    return ;
}

类 Dinic

思路: 顾名思义,就是用 SPFA 跑出残量网络的费用最短路以进行分层,然后跑 Dinic 算法。可以理解为 SPFA 跑出最小费用增广图,然后再让 Dinic 在增广图上跑最大流进行增广。当然,Dinic 仍然可以加上弧优化,不过由于费用的限制,此处不能使用 ISAP 优化。

注意: 由于存在负权边,并且增广图不是一棵树,因此 dfs 的时候不能够处理为只判断 dis[u] + c == dis[v]还必须判 vis[v] == false,否则会陷入由负权边带来的死循环当中。

inline bool SPFA() {
    memcpy(cur, head, sizeof(cur));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    vis[s] = ++cnt;
    // 为加速,vis 改为使用时间戳
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (register int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to, w = edge[i].w, c = edge[i].c;
            if (w > 0 && dis[u] + c < dis[v]) {
                // SPFA 只用于跑出残量网络的最短路
                dis[v] = dis[u] + c;
                if (vis[v] != cnt) {
                    vis[v] = cnt;
                    q.push(v);
                }
            }
        }
    }
    return dis[t] != 0x3f3f3f3f;
}

int dfs(int u, int flow) {
    if (u == t)
        return flow;
    stp[u] = cnt;
    // stp[u] 记录当前增广图上 u 是否已被搜过
    // 只要一搜到 u 就必须记录 stp[u]
    int used = 0;
    for (register int i = cur[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w, c = edge[i].c;
        cur[u] = i;
        // 弧优化
        if (stp[v] != cnt && dis[u] + c == dis[v] && w > 0) {
            // 必须满足 v 没有被搜过才能继续搜 v
            int inc = dfs(v, min(flow, w));
            if (inc > 0) {
                edge[i].w -= inc;
                edge[i ^ 1].w += inc;
                used += inc;
                flow -= inc;
                if (!flow)
                    return used;
            }
        }
    }
    return used;
}

inline void dinic() {
    cnt = 0;
    while (SPFA()) {
        cnt++;
        int inc = dfs(s, 0x7fffffff);
        // inc 为流量增量
        maxflow += inc;
        mincost += inc * dis[t];
    }
    return ;
}

DAY 2

有上下界的网络流

参考资料 CSDN

三张图描述基本思想:

imagebb765f9f11ce7dd5.png image5ea5d329b6138b22.png image.png

其中,图 3 中的绿色节点是 附加源 $x$(6 号节点) 以及 附加汇 $y$(5 号节点),为引入的两个额外节点。对于一条边 $<u,v>:w\in[l,r]$,把这条边拆成: $$\begin{aligned}<u,v>:w&=l;\\<x,v>:w&=l;\\<u,v>:w&=r-l.\end{aligned}$$ 假设与 $x,y$ 相连的所有边都是满流,那么只要剩下的节点满足流量平衡(流入 $=$ 流出),整张图就存在可行流。

等价转化以后,可知:

$$\text{存在可行流}\Leftrightarrow f_{max}(x,y)=\sum_{<u,x>\in E} c(u,x).$$

无源汇网络流

定义: 没有源点和汇点,图上所有点都必须满足流量平衡( $\forall u,\forall v,f(u,v)+f(v,u)=0$)。这种图没有最大流 / 最小流的说法,但是可以判断是否存在可行流:增加一个源点和汇点,按照上述方法等价转化,然后跑最大流即可。

有源汇网络流

定义: 有源点和汇点,可以看作是在无源汇图上加上了一条特殊边 $<t,s>:w=\infty$。那么在跑出 $f_{\max}(x,y)$之后,残量网络中 $<t,s>$的反向边 $<s,t>$上的流量(也就是 $c(s,t)$)即为整张图的一个可行流大小。

最小流

考虑先跑出 $F_1=f_{\max}(x,y)$,在 $<s,t>$上获得一个可行流;然后断掉所有与 $x,y$相连的边(实际操作中,由于可行流已经把这些边流满,因此可以不用管这一步)以及 $s,t$之间的边,在残量网络上跑出 $F_2=f_{\max}(t,s)$(注意是 $t\rightarrow s$),表示可以退回的流量。则对于原图: $$F_{\min}=F_1-F_2$$

最大流

与最小流类似,先跑出 $F_1=f_{\max}(x,y)$;然后断掉额外边,跑出 $F_2=f_{\max}(s,t)$(注意是 $s\rightarrow t$),表示在可行流基础上可以再流的流量。则对于原图: $$F_{\max}=F_1+F_2$$

最大流最小割定理

定义: 对于一个网络图 $G$,若能把图上的点划分为两个点集 $S,T=V-S$,其中 $s\in S,t\in T$,则这个划分方式 $(S,T)$为图的一个割。用 $c(s,t)=\sum_{u\in S,v\in T}c(u,v)$来表示割的容量,最小割即 $c_{\min}(s,t)$。

定理: $$c_{\min}(s,t)=f_{\max}(s,t)$$

简单证明: 显然任意流 $\leq$任意割。当达到最大流,由于 $s,t$之间已经无法增广(没有通路),因此一定能够构造出一个割 $(S,T)$使得 $c(S,T)=f_{\max}(s,t)$。此时,割的容量达到最小值。

输出方案

得到最大流以后,在残量网络中从 $s$开始跑出一个联通块,那么这个连通块内的点组成的集合就是 $S$。

DAY 3

欧拉定理

$$e^{i\theta}=\cos\theta+i\cdot \sin\theta$$

虚数的相关概念

任取复数 $a,b$,辐角分别是 $\alpha,\beta$,则: $$a=|a|\cdot e^{i\cdot \alpha},b=|b|\cdot e^{i\cdot \beta}.$$ $$a\times b=|a|\cdot |b|\cdot e^{i\cdot(\alpha+\beta)}.$$ 所以复数乘法的几何意义是向量的伸缩和旋转。 $a\times b$ 的几何意义是使复平面上 $a$所对应的向量 $\vec{a}$ 的模长变为原来的 $|b|$ 倍,并逆时针旋转角度 $\beta$ 所得到的向量。

用极坐标表示,设 $\vec{a}=(r_1,\alpha),\vec{b}=(r_2,\beta)$,复数 $a\times b=c$,则有: $$\vec{c}=(r_1\cdot r_2,\alpha+\beta).$$

单位复根

将单位圆等分成 $n$个部分(以单位圆与实轴正半轴的交点为第一个等分点),以原点为起点,圆的这 $n$个 $n$等分点为终点,作出 $n$个向量。 其中幅角为正且最小的向量称为 $n$次单位向量,记为 $\omega_n^1$。其余的向量就分别为 $\omega_n^2,\omega_n^3,\cdots,\omega_n^n$。

那么显然有以下性质: $$\omega_n^n=\omega_n^0=1,$$ $$\omega_n^k=e^{2\pi\cdot\frac kni}=\cos(2\pi\cdot\frac kn)+\sin(2\pi\cdot\frac kn).$$ $$\omega_{2n}^{2k}=\omega_n^k\Rightarrow \omega_{mn}^{mk}=\omega_n^k.\text{(折半引理)}$$ $$\omega_n^{k+\frac 2n}=-\omega_n^k.\text{(消去引理)}$$

快速傅里叶变换

DFT

设一个 $n-1$(其中 $n=2^k,k\in \text{N}$)阶多项式 $f(x)=\sum_{i=0}^{n-1} a_i\cdot x^i$。如果在曲线上取 $n$个互不相同的点,就可以由 高斯消元法 唯一确定所有项的系数。

以 $7$阶多项式(8 个项)为例,设 $$f(x)=a_0+a_1x^1+a_2x^2+\cdots+a_7x^7.$$ 再设 $$\begin{aligned}h(x)=a_0+a_2x^1+a_4x^2+a_6x^3,\\g(x)=a_1+a_3x^1+a_5x^2+a_7x^3.\end{aligned}$$ $$\Rightarrow f(x)=h(x^2)+x\cdot g(x^2).$$ 假设带入的自变量 $x=\omega_n^k$,则 $$f(\omega_n^k)=h(\omega_n^{2k})+\omega_n^k\cdot g(\omega_n^{2k}).$$ $$\begin{aligned}\Rightarrow f(\omega_n^k)&=h(\omega_{\frac n2}^k)+\omega_n^k\cdot g(\omega_{\frac n2}^k),\\f(\omega_n^{k+\frac n2})&=h(\omega_{\frac n2}^k)-\omega_n^k\cdot g(\omega_{\frac n2}^k)\end{aligned}$$ 由于 $k,k+\frac n2$取遍了 $[0,n-1]$中的所有整数,也就是说取了互不相同的 $n$个自变量 $x_i$的值带入 $f(x)$,所以根据获得的 $y_i=f(x_i)$,一定可以反算出所有项的系数。

所以对于多项式 $f(x)=\sum_{i=0}^{n-1}a_i\cdot x^i$,把它转化为 $n$个值 $y_k=f(\omega_n^k)$的过程就叫 DFT。

再观察上面的表达式,可以发现 $h(x),g(x)$的规模都是 $f(x)$的一半(观察 $\omega$的下标可得),因此可以递归成两个子问题求解,DFT 的复杂度由朴素代入的 $O(n^2)$降为 $O(n\log n)$。

imagee6b214bba501e360.png $$\footnotesize\text{图源:OI Wiki}$$ 观察规律:原来序列,每个数的下标用二进制表示,然后把二进制翻转对称一下,就是最终那个位置的下标。这个方法可以把递归变为循环。

实现时需要预处理 rev[i] 表示 i 的二进制为翻转后的值:

    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

IDFT

在 DFT 以后,设 $y_i=f(w_n^i)$,则系数方程可以用下面这样一个矩阵运算式表示:

image.png $$\footnotesize\text{图源:OI Wiki}$$ 简化为: $Y=X\times A$ 那么为了求得 $A$,只需要左右同时左乘 $X$的逆矩阵(设为 $X^{-1}$),也就是说: $$A=Y\times X^{-1}$$ 代入 $X\times X^{-1}=D\text{(单位矩阵)}$可得: $$X^{-1}_{j,k}\cdot X_{j,k}=\frac 1n$$ 观察矩阵运算式,于是有: $$X_{j,k}^{-1}=\frac 1nw_n^{-k\cdot j}$$ $$\Rightarrow a_j=\frac 1n\sum_{k=0}^{n-1}y_k\cdot w_n^{-k\cdot j}$$ 可以发先这个式子等价于把 $\omega_n$换为 $\omega_n^{-1}$,并且再乘上 $n^{-1}$的 DFT,所以就可以合二为一,用一个 fft() 函数一起写。

#include <bits/stdc++.h>
using namespace std;
const double pi   = acos(-1.0);
const int    MAXN = 3e6 + 10;
// 开 2 倍空间似乎不够,多多益善
struct Complex {
    double x, y;
    Complex(double src_x, double src_y) {
        x = src_x;
        y = src_y;
    }
    Complex() {}
    Complex operator + (const Complex &b) const {
        return Complex(x + b.x, y + b.y);
    }
    Complex operator - (const Complex &b) const {
        return Complex(x - b.x, y - b.y);
    }
    Complex operator * (const Complex &b) const {
        return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
    }
};
Complex a[MAXN], b[MAXN];
int rev[MAXN]; // 用于保存 i 二进制翻转以后的数
int n, m, l = 0;

inline void fft(Complex y[], int len, int flag) {
    for (int i = 0; i < len; i++)
        if (i < rev[i])
            swap(y[i], y[rev[i]]);
    // 预处理
    for (int h = 2; h <= len; h <<= 1) {
        // h: 合并区间的长度
        Complex wn(cos(pi * 2 / h), sin(pi * 2 * flag / h));
        // 计算单位复根
        for (int j = 0; j < len; j += h) {
            Complex w(1, 0);
            // w 保存当前代入的值
            for (int k = j; k < j + (h >> 1); k++, w = w * wn) {
                Complex u = y[k];
                Complex v = w * y[k + (h >> 1)];
                y[k] = u + v;
                y[k + (h >> 1)] = u - v;
            }
        }
    }
    if (flag == -1)
        for (int i = 0; i < len; i++)
            y[i].x /= len;
    // IDFT 中的 1 / n 系数
    return ;
}

inline int read() {
    register int  res = 0, flag = 0;
    register char ch  = getchar();
    while (!isdigit(ch))
        ch == '-' ? flag = 1, ch = getchar() : ch = getchar();
    while (isdigit(ch))
        res = (res << 3) + (res << 1) + (ch ^ '0'), ch = getchar();
    return flag ? -res : res;
}

int main() {
    n = read(), m = read();
    while ((1 << l) <= n + m)
        l++;
    for (int i = 0; i <= n; i++)
        a[i].x = read();
    for (int i = 0; i <= m; i++)
        b[i].x = read();
    for (int i = 0; i < (1 << l); i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    // 预处理 rev[]
    fft(a, 1 << l, 1);
    fft(b, 1 << l, 1);
    for (int i = 0; i <= (1 << l); i++)
        a[i] = a[i] * b[i];
    // DFT 完成以后,合并 f(x) 与 g(x) 信息供 IDFT 使用
    fft(a, 1 << l, -1);
    for (int i = 0; i <= n + m; i++)
        printf("%d ", int(a[i].x + 0.5)); // 四舍五入排除精度损失
    return 0;
}

DAY 4

退役了