Bzoj 1002(递推+高精度)

BZOJ 1002
由基尔霍夫矩阵树定理推出递推式
$$dp(n)=3dp(n-1)-dp(n-2)+2$$
初值$dp(1)=1, dp(2)=5$,然后答案很大需要高精度,这题也作为一个练习高精度的题目了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct data {
int len, a[105];
};
data mul(data a, int b) {//*
for (int i=1;i<=a.len;i++) {
a.a[i] *= b;
}
int jw = 0;
for (int i=1;i<=a.len+1;i++) {
a.a[i] = a.a[i] + jw;
jw = a.a[i] / 10;
a.a[i] %= 10;
}
if (a.a[a.len+1] != 0) a.len++;
return a;
}
data sub(data a, data b) {//-
a.a[1] += 2;
for (int i=1;i<=a.len;i++) {
if (a.a[i] - b.a[i] < 0) {
a.a[i] += 10, a.a[i+1]--;
}
b.a[i] = a.a[i] - b.a[i];
}
b.len = a.len;
while (b.a[b.len] == 0) b.len--;
return b;
}
int n;
void clean() {
}
void solve() {
clean();
if (n <= 2) {
if (n == 1) printf("1\n");
else printf("5\n");
}
data a, b, c;
ms(a.a, 0), ms(b.a, 0), a.a[1] = 5, b.a[1] = 1, a.len = b.len = 1;
for (int i=3;i<=n;i++) {
c = sub(mul(a, 3), b);
b = a, a = c;
}
for (int i=a.len;i>0;i--) printf("%d", a.a[i]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------