You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
47 lines
918 B
47 lines
918 B
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
// 棋盘覆盖问题原理
|
|
// https://blog.csdn.net/m0_51005809/article/details/120112637
|
|
|
|
const int N = 1e5 + 10;
|
|
int a[N], al;
|
|
|
|
void mul(int a[], int &al, int b) {
|
|
int t = 0;
|
|
for (int i = 1; i <= al; i++) {
|
|
t += a[i] * b;
|
|
a[i] = t % 10;
|
|
t /= 10;
|
|
}
|
|
while (t) {
|
|
a[++al] = t % 10;
|
|
t /= 10;
|
|
}
|
|
while (al > 1 && !a[al]) al--;
|
|
}
|
|
|
|
int r;
|
|
void div(int a[], int &al, int b, int &r) {
|
|
r = 0;
|
|
for (int i = al; i >= 1; i--) {
|
|
r = r * 10 + a[i];
|
|
a[i] = r / b;
|
|
r %= b;
|
|
}
|
|
while (al > 1 && !a[al]) al--;
|
|
}
|
|
|
|
int main() {
|
|
int k;
|
|
cin >> k;
|
|
//通过高精度计算4^k
|
|
a[1] = 1, al = 1;
|
|
for (int i = 1; i <= k; i++) mul(a, al, 4);
|
|
|
|
div(a, al, 3, r);
|
|
for (int i = al; i; i--) printf("%d", a[i]);
|
|
return 0;
|
|
}
|