「Bzoj 1002」「FJOI2007」轮状病毒 (递推+高精度)

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

#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;
}