hdu 5459 Jesus is Here

acm dp

很明顯是dp, 但找推導公式也花了一點時間

hdu5459.cpp
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
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <cstring>

typedef long long ll;
const ll MOD = 530600414;
const int MAXN = 201315;

ll R[MAXN], C[MAXN];
ll F[MAXN], B[MAXN], N[MAXN];

/**
c
ff
cff                                                                         | F 0 B 2
ffcff                       0    | 2                                        | F 2 B 2 | 2+2+1
cff ffcff                   5    | 0   (+3) 2  -> 5                         | F 5 B 9 | (F3 + F4 + N3*C4) = 5 B (B3 + B4 + N4*C3) = 9
ffcff cffffcff              16   | 2   (+5) 0 5 -> 5-2 + 10-2 + 10-5 = 16   | F 17
cffffcff ffcffcffffcff      88   | 0 5  (+8) 2 5 10 ->


F5 = F3 + F4 + N3*C4
B5 = B3 + B4 + N4*C3
Rn = Rn-1 + Rn-2 + Bn-2 * Cn-1 + Fn-1 * Cn-2 + Cn-1*C-2

0 + 0 + 2*1 + 2*1 + 1*1 = 5
0 + 5 + 2*2 + 5*1 + 1*2  = 16
16 + 5 + 9*3 + 17*2 + 2*3 = 88


N: length
C: number of c
F: front sum ex: ffc = 2 ffcfc = 2+4 = 6
B: back sum
R: result

one result can be seem as --> R[n-1]+R[n-2]+something
R[n-1], R[n-2] is all the distinct combination of c in that range.
so something should be the combination that across this two range.
If we draw a picture of the distance that across two sector.
we could find that it is a combination of B and R which can also use a formula to find.
*/

void init() {

    R[3] = R[4] = 0;
    F[3] = 0; F[4] = 2;
    B[3] = 2; B[4] = 2;
    N[3] = 3; N[4] = 5;
    C[3] = 1; C[4] = 1;

    for(int i = 5; i < MAXN; ++i) {
        R[i] = ((R[i-1]+R[i-2])%MOD + (B[i-2]*C[i-1])%MOD + (F[i-1]*C[i-2])%MOD + (C[i-1]*C[i-2])%MOD)%MOD;
        F[i] = ((F[i-2] + F[i-1])%MOD + (N[i-2]*C[i-1])%MOD)%MOD;
        B[i] = ((B[i-2] + B[i-1])%MOD + (N[i-1]*C[i-2])%MOD)%MOD;
        N[i] = (N[i-1] + N[i-2])%MOD;
        C[i] = (C[i-1] + C[i-2])%MOD;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    init();
    int ncase;
    scanf("%d", &ncase);
    for(int t = 1; t <= ncase; ++t) {
        int k;
        scanf("%d", &k);
        printf("Case #%d: %lld\n", t, R[k]);
    }
    return 0;
}