## 什么是傅里叶变换
傅里叶变换是一种数学工具，用于将一个函数从时域（时间域）转换到频域（频率域）。它是以法国数学家约瑟夫·傅里叶的名字命名的。傅里叶变换可以将一个函数表示为不同频率的正弦和余弦函数的叠加，从而揭示函数在不同频率上的能量分布情况。



傅里叶变换在物理学和工程学中有许多应用。它的基本思想是将一个函数分解为不同特征的正弦函数的和，类似于化学分析中分析化合物的元素成分。对于一个函数，傅里叶变换可以分析其组成部分，确定组成它的基本（正弦函数）成分[[1]](https://zh.wikipedia.org/wiki/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2)。

傅里叶变换的定义有多种方式，但一般情况下，我们使用连续傅里叶变换的定义。连续傅里叶变换将一个可积函数表示成复指数函数的积分形式或级数形式。具体地说，对于一个函数f(x)，它的傅里叶变换表示为：

F[f](ξ) = ∫[-∞, ∞] f(x) e^(-2πixξ) dx [[1]](https://zh.wikipedia.org/wiki/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2)

其中ξ为任意实数，ξ的定义域为频域。傅里叶变换将函数从时域转换到频域，将函数在不同频率上的能量分布情况展示出来。

傅里叶变换具有许多基本性质，其中包括线性性质和平移性质。线性性质表示两个函数的傅里叶变换之和等于各自变换之和。平移性质表示如果一个函数的傅里叶变换存在，那么对于任意实数ω0，函数f(x)e^(iω0x)的傅里叶变换也存在，并且满足以下关系：

F[f(x)e^(iω0x)] = F[f](ω - ω0) [[1]](https://zh.wikipedia.org/wiki/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2)

傅里叶变换在许多领域都有广泛的应用，包括医学、数据科学、物理学、声学、光学、结构力学、量子力学、数论、组合数学、概率论、统计学、信号处理、密码学、大气科学、海洋学、通讯和金融等。例如，在信号处理中，傅里叶变换可以将复杂的信号分解成具有不同振幅的单一频率分量，并用于滤波等操作。在量子力学中，傅里叶变换可以将位置空间的波函数转换为动量空间的波函数。

---
Learn more:
1. [傅里叶变换 - 维基百科，自由的百科全书](https://zh.wikipedia.org/wiki/%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2)
2. [傅里叶变换的数学意义-电子发烧友网](https://www.elecfans.com/d/2238532.html)
3. [计算机视觉-图像的傅里叶变换 - 知乎](https://zhuanlan.zhihu.com/p/554363765)

## 简单应用
```cpp
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cmath>
#define N (1<<18)//如果不介意，可以开小点
using namespace std;
struct cmpx{//不一样的结构体，运算符重载
    double r,i;
    cmpx operator + (const cmpx &a)const{return (cmpx){r+a.r,i+a.i};}
    cmpx operator - (const cmpx &a)const{return (cmpx){r-a.r,i-a.i};}
    cmpx operator * (const cmpx &a)const{return (cmpx){r*a.r-i*a.i,r*a.i+i*a.r};}
};
int rev[N];
cmpx A[N],a[N],b[N],c[N];
int L,n;
void DFT(cmpx a[],int f){
     int i,j,k;
     for(i=0;i<L;i++)
     A[i]=a[rev[i]];
     for(i=0;i<L;i++)
     a[i]=A[i];
     for(i=2;i<=L;i<<=1){
                         cmpx wi=(cmpx){cos(2.0*M_PI/i),f*sin(2.0*M_PI/i)};
                         for(k=0;k<L;k+=i){
                                           cmpx w=(cmpx){1.0,0.0},x,y;
                                           for(j=0;j<i/2;j++){
                                                              x=a[k+j];
                                                              y=w*a[k+j+i/2];
                                                              a[k+j]=x+y;
                                                              a[k+j+i/2]=x-y;
                                                              w=w*wi;
                                                              }
                                           }
                         }
  if(f==-1)
  for(i=0;i<L;i++)
  a[i].r/=L;
}
void FFT(cmpx a[],cmpx b[],cmpx c[]){
     int i;
     DFT(a,1);
     DFT(b,1);
     for(i=0;i<L;i++)
     c[i]=a[i]*b[i];
     DFT(c,-1);
}
void init(int tmp){
     int i,t,j;
     for(n=0,L=1;L<tmp;L<<=1)
     n++;
     n++;
     L<<=1;
     for(i=0;i<L;i++)
     for(t=i,j=0;j<n;j++){
         rev[i]<<=1;
         rev[i]|=t&1;
         t>>=1;
         }
}
int ans[N];
void DSC(){//开始处理问题，开始处理问题，开始处理问题，重要的事情说3遍！
     int l1=0,l2=0,i;
     char ch=getchar();
     while(ch>'9'||ch<'0')
     ch=getchar();
     while(ch>='0'&&ch<='9'){
                             a[l1].r=ch-'0';
                             a[l1++].i=0.0;
                             ch=getchar();
                             }
     while(ch>'9'||ch<'0')
     ch=getchar();
     while(ch>='0'&&ch<='9'){
                             b[l2].r=ch-'0';
                             b[l2++].i=0.0;
                             ch=getchar();
                             }
    reverse(a,a+l1);
    reverse(b,b+l2);
    init(max(l1,l2));
    FFT(a,b,c);
    for(i=0;i<L;i++)
    ans[i]=(int)(c[i].r+0.5);
    for(i=0;i<L;i++){
                     ans[i+1]+=ans[i]/10;
                     ans[i]%=10;
                     }
    L=l1+l2+1;
    while(!ans[L]&&L>0)
    L--;
    for(i=L;~i;i--)
    putchar(ans[i]+'0');
    putchar('\n');
}
int main(){//主函数so easy
    DSC();
    return 0;
}
```
这份代码实现了整数的快速 Fourier 变换(FFT)来进行大整数的乘法。

主要步骤:

1. 定义复数结构体 cmpx,重载基本四则运算。

2. 定义FFT参数:
   - rev按位翻转数组,用于快速傅立叶变换复杂度优化。
   - A为FFT工作数组。
   - init函数初始化FFT参数。

3. DFT函数实现离散傅立叶变换,参数f区分正变换(1)和逆变换(-1)。

4. FFT函数调用DFT实现整数 FFT 乘法:
   - a,b长度分别FFT
   - 点乘得出结果c 
   - 调用DFT实现FFT乘法

5. DSC函数开始处理问题:
   - 读入整数a,b
   - 调用FFT函数乘法
   - 整形四舍五入取整数部分
   - 返回乘法结果

6. main函数调用DSC函数,完成大整数乘法运算。

整体采用FFT算法优化整数乘法计算复杂度,使得很大整数进行乘法也能在很短时间内得到结果。实现了详细的注释来解释每一步的目的。

FFT算法

pivot_root是一个系统调用，用于更改进程的根文件系统。它将当前进程的根文件系统移动到put_old目录，并将new_root设为新的根文件系统。pivot_root系统调用需要在用户命名空间中拥有CAP_SYS_ADMIN特权[[1]](https://www.ibm.com/docs/en/zos/3.1.0?topic=descriptions-pivot-root-bpx1pvr-bpx4pvr-change-root-mount)。



使用pivot_root系统调用需要满足以下条件：
- new_root和put_old必须是目录。
- new_root和put_old不能在当前根文件系统的相同挂载点上。
- put_old必须在new_root下，也就是说，通过在put_old路径后添加一些非负数的"../"后缀，应该得到与new_root相同的目录。
- new_root必须是一个挂载点的路径，但不能是"/"。如果一个路径还不是挂载点，可以通过将该路径绑定到自身来将其转换为挂载点。
- new_root的父挂载点和当前根目录的父挂载点的传播类型不能为MS_SHARED。同样，如果put_old是一个现有的挂载点，它的传播类型也不能为MS_SHARED。这些限制确保pivot_root系统调用不会将任何更改传播到另一个挂载命名空间。
- 当前根目录必须是一个挂载点[[2]](https://man7.org/linux/man-pages/man2/pivot_root.2.html)。

pivot_root系统调用的返回值：
- 成功时返回0。
- 失败时返回-1，并设置errno来指示错误[[2]](https://man7.org/linux/man-pages/man2/pivot_root.2.html)。

pivot_root系统调用可能会失败，并返回以下错误之一：
- EBUSY：new_root或put_old在当前根挂载点上。这种情况通常发生在new_root是"/"的情况下。
- EINVAL：new_root不是一个挂载点。
- EINVAL：put_old不在new_root下。
- EINVAL：当前根目录不是一个挂载点（因为之前进行了chroot操作）。
- EINVAL：当前根目录在rootfs（初始ramfs）挂载上。
- EINVAL：new_root的挂载点或其父挂载点的传播类型为MS_SHARED。
- EINVAL：put_old是一个挂载点，并且其传播类型为MS_SHARED。
- ENOTDIR：new_root或put_old不是目录。
- EPERM：调用进程没有CAP_SYS_ADMIN特权[[2]](https://man7.org/linux/man-pages/man2/pivot_root.2.html)。

---
Learn more:
1. [pivot_root (BPX1PVR, BPX4PVR) — Change the root mount](https://www.ibm.com/docs/en/zos/3.1.0?topic=descriptions-pivot-root-bpx1pvr-bpx4pvr-change-root-mount)
2. [pivot_root(2) - Linux manual page](https://man7.org/linux/man-pages/man2/pivot_root.2.html)
3. [pivot_root(8) - Linux manual page](https://man7.org/linux/man-pages/man8/pivot_root.8.html)

pivot_root系统调用

![image.png](/static/img/7551a468ac3ce83435782ea9fade1b71.image.webp)

> 1 ^ 3 = 2
> 
> 2 ^ 3 = 1
> 



```cpp
class Solution {
public:
    int magicalString(int n) {
        int res = 0;
        int tag = 2;
        string s1 = "";
        string s2 = "12";
        for (int i = 0; i < n; i++) {
            if (i >= s2.size()) s2 = s1;
            if (s2[i] == '1') res++;
            for (int j = 0; j < s2[i] - '0'; j++) {
                s1 += (tag^3) + '0';
            }
            tag ^= 3;
        }
        return res;
    }
};
```

双指针3

Merkle Tree是一种用于完整性校验的数据结构，也被称为哈希树。它由计算机科学家Ralph Merkle提出，并以他的名字命名。Merkle Tree在点对点网络、Git版本控制系统、IPFS协议以及比特币和以太坊等项目中得到广泛应用。



哈希（Hash）是Merkle Tree的基础概念。哈希是一种将数据转换为固定长度字符串的算法。通过对数据进行哈希运算，可以得到一个唯一的哈希值。即使数据发生微小变化，其哈希值也会完全不同。因此，通过比较哈希值，可以检查数据是否被损坏或篡改。

在点对点网络中，数据通常被分割成多个小块进行下载，并且存在不稳定或不可信的机器。为了解决这个问题，可以使用哈希列表（Hash List）。哈希列表是由多个数据块的哈希值组成的列表，这些哈希值之间存在兄弟关系。通过下载种子文件（包含哈希列表），可以从任意机器上下载数据块，并通过根哈希来验证每个哈希的正确性。

Merkle Tree是在哈希列表的基础上引入了树形结构，以获得更高的灵活性。在Merkle Tree中，数据被分成小块，并计算每个块的哈希值。然后，将相邻的两个哈希值合并成一个字符串，并计算该字符串的哈希值，得到一个新的哈希值。这个过程不断重复，直到最终形成一棵倒挂的树，树根被称为Merkle Root。Merkle Tree可以用于验证大型数据的完整性。

---
Learn more:
1. [Merkle Tree - 知乎](https://zhuanlan.zhihu.com/p/103372259)
2. [区块链技术与应用-note - 知乎](https://zhuanlan.zhihu.com/p/635292249)
3. [https://zhuanlan.zhihu.com/p/22642813？ - 知乎](https://www.zhihu.com/question/51062163)

merkle树

![image.png](/static/img/85c71013771317487b1f1f93b81ba747.image.webp)



```cpp
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
  sort(g.begin(), g.end());
  sort(s.begin(), s.end());
  
  int i = 0, j = 0, ans = 0;
  
  while(i < g.size() && j < s.size()) {
    if(g[i] <= s[j]) {
      ans++;
      i++;
      j++;
    } else {
      j++;
    }
  }
  
  return ans;
}
};
```