<span>算法模板：大数乘法，并查集</span>

大数乘法：

• 模拟乘法手算累加:

  • 和小学生一样竖式计算，逐位相乘，结果相加(很麻烦)

  • 改进：先不算任何进位，只保存每一位结果，最后从右到左相加

    int result[num1.length+num2.length]; //结果不会比俩数长度加起来还长
    for(int i=0; i<num1.size(); i++) {
        for(int j=0; j<num2.size(); j++) { 
          	//不考虑进位，先乘了再说
            result[i+j+1] += num1[i] * num2[j];
            //+1位给最后最高位进位留空间
        } 
    }
    
    //单独处理进位
    for(int k = result.size()-1; k>0 ; k--) {
        if(result[k] > 10) {
            result[k-1] += result[k] / 10;
            result[k] %= 10;
        }
    }
    

• 分治乘法：

• 快速数论变换(FNTT):

• 中国剩余定理:

并查集

• 原理：连接成一个通路的拥有一个共同的父节点

• 应用：连通路问题，并联计算

• 模板：

  find寻找父节点

  • 非递归版

  int find(int x) {
      while(x != pre[x]) {
          x = pre[x] = pre[pre[x]]; //路径压缩
      }
      return x;
  }
  

  • 递归版

  int find(int x) {
      return x == pre[x] ? x : pre[x] = find(pre[x]); 
  }
  

  union联合两个分支

  void Union(int x,int y) {
      int fx = find(x);
      int fy = find(y);
      if(fx != fy) {
          pre[fx] = fy;
      }
  }