Algorithm7 分治算法 & 快速幂
[TOC]
分治问题
最典型：分形 & 矩阵的分治
矩形分治的 统一解法 // 模版：数据结构用一个统一的数组来存储 图//矩阵 结构【init】，然后 分形//分治 递归【draw】，最后再画出来【print】（或者有的时候需要输出分治的过程）
矩阵的分治：https://www.luogu.com.cn/problem/P5461
题目大意：正方形矩阵，分成四块，左上全赦免（为零），然后对剩下其他部分接着分成四块，一直这样下去。输出最后矩阵
#include <iostream>
using namespace std;
#define maxl 1030
int n, a[maxl][maxl];
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))
#include <cmath>
void draw(int x, int y, int h) {
if (h == 2) {a[x+1][y] = a[x][y+1] = a[x+1][y+1] = 1;return;}
int nowh = h>>1;
draw(x+nowh, y, nowh);
draw(x, y+nowh, nowh);
draw(x+nowh, y+nowh, nowh);
}
void print() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
printf("%d ", a[i][j]);
}
printf("\n");
}
}
int main() {
scanf("%d", &n); n = pow(2, n);
cl(a, 0); // init
draw(1, 1, n); // draw
print(); // print
return 0;
}
分形-谢尔宾斯基三角：https://www.luogu.com.cn/problem/P1498
#include <iostream>
using namespace std;
#define maxl 1030
int n, a[maxl][maxl];
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))
#include <cmath>
void draw(int x, int y, int h) {
if (h == 2) {
a[x][y] = 1;
return;
}
int nowh = h >> 1;
for (int i = x; i < x + nowh; ++i)
for (int j = y; j < y + nowh; ++j)
a[i][j] = 1;
draw(x, y + nowh, nowh);
draw(x + nowh, y, nowh);
draw(x + nowh, y + nowh, nowh);
}
void print() {
for (int i = 1; i <= n; i++) {
int j = 1;
while (a[i][j]) {printf(" ");j++;}
for (; j <= n; j++) {
if (i & 1) {
if (a[i][j] == 0)printf("/\\");
else printf(" ");
} else {
if (a[i][j] == 0) {
printf("/__\\");
j++;
} else printf(" ");
}
}
printf("\n");
}
}
int main() {
scanf("%d", &n);
n = pow(2, n);
cl(a, 0); // init
draw(1, 1, n); // draw
print(); // print
return 0;
}
分治思想
https://www.luogu.com.cn/problem/P1228
题目大意：用四种形状来覆盖正方形
思路：分成四个大块，然后把没有点的那个模块的剩下三个模块的端点给覆盖上即可。
#include <iostream>
using namespace std;
#define maxl 1030
int k, x, y, a[maxl][maxl];
#include <cmath>
#include <cstring>
#define cl(a, b) memset(a, b, sizeof(a))
void draw(int x, int y, int h) {
if (h >= 2) {
int nowh = h>>1;
for (int i = x; i < x+h; ++i) {
for (int j = y; j < y+h; ++j) {
if (a[i][j]) {
if (i<x+nowh && j<y+nowh) {a[x+nowh][y+nowh] = a[x+nowh-1][y+nowh] = a[x+nowh][y+nowh-1] = 1;printf("%d %d 1\n", x+nowh, y+nowh);}
else if (i>=x+nowh && j<y+nowh) {a[x+nowh][y+nowh] = a[x+nowh-1][y+nowh-1] = a[x+nowh-1][y+nowh] = 2;printf("%d %d 3\n", x+nowh-1, y+nowh);}
else if (i<x+nowh && j>=y+nowh) {a[x+nowh][y+nowh] = a[x+nowh][y+nowh-1] = a[x+nowh-1][y+nowh-1] = 3;printf("%d %d 2\n", x+nowh, y+nowh-1);}
else if (i>=x+nowh && j>=y+nowh) {a[x+nowh-1][y+nowh-1] = a[x+nowh-1][y+nowh] = a[x+nowh][y+nowh-1] = 4;printf("%d %d 4\n", x+nowh-1, y+nowh-1);}
draw(x, y, nowh);draw(x+nowh, y, nowh);draw(x, y+nowh, nowh);draw(x+nowh, y+nowh, nowh);
return;
}
}
}
}
}
int main() {
scanf("%d%d%d", &k, &x, &y); k = pow(2, k);
cl(a, 0); a[x][y] = 5; // init
draw(1, 1, k); // draw
return 0;
}
快速幂
题目大意：求a的b幂。
1、任何数都可以写成2的a次幂+2的b次幂+……这样，类比任何数都有二进制来表示，二进制就是2的各个位数次幂进行相加。
2、自相乘base *= base就可以将幂次翻倍，也就刚好达到按位移动的道理。
3、看看这个数的幂次是否需要乘进去，就让当前的数来按位与上1&1，这样就可以判断最后一位是否是1，也就是自乘出来的这一次是否需要乘进去。
4、通过按位移动，来看不同位数，从而看这个幂次的组成。
// 计算a的k次方
int quickPower(int a, int k){
int ans = 1, base = a; // base就是a的1次幂，然后再自乘就是a的2次幂，再自乘就是a的4次幂，再自乘就是a的8次幂
while (k > 0) {
if (k & 1) ans *= base;
base *= base;
k >>= 1;
}
return ans;
}
快速幂取余
// 计算a的k次方再取余
ll quickPowerwithMod(ll a, ll k, ll m){
ll ans = 1, base = a; // base就是a的1次幂，然后再自乘就是a的2次幂，再自乘就是a的4次幂，再自乘就是a的8次幂
while (k > 0) {
if (k & 1) {ans *= base; ans %= m;}
base *= base; base %= m;
k >>= 1;
}
return ans;
}