-
大數乘法：
-
模擬乘法手算累加:
-
和小學生一樣豎式計算，逐位相乘，結果相加(很麻煩)
-
改進：先不算任何進位，只保存每一位結果，最后從右到左相加
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; } }
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/101263.html
標籤：其他