HDU 5451 Best Solver

acm math

兩種推法

1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(5 + 2*sqrt(6)) ^ n = An + Bn*sqrt(6)

f(n) = [(5 + 2*sqrt(6))] * [An-1 + Bn-1*sqrt(6)]
     = (5*An-1 + 12*Bn-1) + (2*An-1 + 5*Bn-1)*sqrt(6)


5   12          An-1      An
2   5     *     Bn-1   =  Bn

A1 = 5, B1 = 2

[An + Bn*sqrt(6)] + [An - Bn*sqrt(6)] = 2*An
因為(5 - 2*sqrt(6))比1小比0大, 他的n次方也一定比1小比0大
我們把這當1
[An + Bn*sqrt(6)] = 2*An - 1
Answer = = 2*An - 1

而因為n很大, 而mod小, 我們知道不停乘同一個數, 而且mod同一個mod, 會最終出現重複 (在n-1個格子中放入n個球, 一定有一個格子有至小2個球)
而且會是不停重複 ex: 1 2 3 1 2 3 1 ....
我們可以找出開始重複的位置

我覺得這個比較容易推, 但我看別人的解都是第二種

hdu5451.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;


const int MAXMOD = 47000;
const int MAXMAT = 3;
typedef long long ll;
ll MOD;
ll rMOD[MAXMOD];
ll ans[MAXMOD];


struct Mat {
    ll v[MAXMAT][MAXMAT];
    int n, m; // n rows, m columns
    Mat() {}
    Mat(int a, int b) {
        n = a;
        m = b;
        memset(v, 0, sizeof(v));
    }
    Mat operator * (const Mat &b) {
        Mat res(n, b.m);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < b.m; ++j)
                for(int k = 0; k < m; ++k) {
                    res.v[i][j] = (res.v[i][j] + (v[i][k]*b.v[k][j])%MOD)%MOD;
                }
        return res;
    }
};

void find_rMod(ll x) {
    ans[0] = 2;
    ans[1] = 10;

    // a = 5, b = 24
    // Cn+1 = 2aCn - (a^2-b)*Cn-1
    for(int i = 2; i < MAXMOD; ++i) {
        ans[i] = (10LL * ans[i-1] - ans[i-2] + MOD)%MOD;
        if(ans[i-1] == ans[0] && ans[i] == ans[1]) {
            rMOD[MOD] = i - 1;
            return;
        }
    }
}

Mat mat_pow(Mat x, ll pow) {
    Mat res(x.n, x.m);

    for(int i = 0; i < x.n; ++i) {
        res.v[i][i] = 1;
    }

    while(pow) {
        if(pow & 1) res = res*x;
        x = x*x;
        pow >>= 1;
    }

    return res;
}

ll ll_pow(ll x, ll pow) {
    ll res = 1;

    while(pow) {
        if(pow & 1) res = (res*x)% rMOD[MOD];
        x = (x*x) % rMOD[MOD];
        pow >>= 1;
    }

    return res;
}

ll solve(ll n) {
    find_rMod(MOD);

    Mat base(2, 1);
    Mat func(2, 2);
    base.v[0][0] = 5%MOD;
    base.v[1][0] = 2%MOD;

    func.v[0][0] = 5%MOD;
    func.v[0][1] = 12%MOD;
    func.v[1][0] = 2;
    func.v[1][1] = 5;

    ll rfuncp = ll_pow(2, n);
    Mat rfunc = mat_pow(func, rfuncp);
    base = rfunc*base;
    return ((2*base.v[0][0])%MOD - 1 + MOD)%MOD;
}

int main() {
    // freopen("input.txt", "r", stdin);
    memset(rMOD, -1, sizeof(rMOD));
    ll n;
    int ncase;
    scanf("%d", &ncase);
    for(int t = 1; t <= ncase; ++t) {
        scanf("%lld%lld", &n, &MOD);
        printf("Case #%d: %lld\n", t, solve(n));
    }
}

  1. 第二種
1
2
3
4
5
6
7
8
9
10
11
12
13
An = (a + sqrt(b)) ^ n
Bn = (a - sqrt(b)) ^ n

Cn = An + Bn
Cn = An - 1


2a   -(a^2-b)          An-1      An
1   0            *     Bn-1   =  Bn

Cn+1  =
Cn*[(a + sqrt(b) + (a - sqrt(b)] = .....
Cn+1 = 2*a*Cn - (a^2-b)*Cn-1
hdu5451
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;


const int MAXMOD = 47000;
const int MAXMAT = 3;
typedef long long ll;
ll MOD;
ll rMOD[MAXMOD];
ll ans[MAXMOD];


struct Mat {
    ll v[MAXMAT][MAXMAT];
    int n, m; // n rows, m columns
    Mat() {}
    Mat(int a, int b) {
        n = a;
        m = b;
        memset(v, 0, sizeof(v));
    }
    Mat operator * (const Mat &b) {
        Mat res(n, b.m);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < b.m; ++j)
                for(int k = 0; k < m; ++k) {
                    res.v[i][j] = (res.v[i][j] + (v[i][k]*b.v[k][j])%MOD)%MOD;
                }
        return res;
    }
};

void find_rMod(ll x) {
    ans[0] = 2;
    ans[1] = 10;

    // a = 5, b = 24
    // Cn+1 = 2aCn - (a^2-b)*Cn-1
    for(int i = 2; i < MAXMOD; ++i) {
        ans[i] = (10LL * ans[i-1] - ans[i-2] + MOD)%MOD;
        if(ans[i-1] == ans[0] && ans[i] == ans[1]) {
            rMOD[MOD] = i - 1;
            return;
        }
    }
}

Mat mat_pow(Mat x, ll pow) {
    Mat res(x.n, x.m);

    for(int i = 0; i < x.n; ++i) {
        res.v[i][i] = 1;
    }

    while(pow) {
        if(pow & 1) res = res*x;
        x = x*x;
        pow >>= 1;
    }

    return res;
}

ll ll_pow(ll x, ll pow) {
    ll res = 1;

    while(pow) {
        if(pow & 1) res = (res*x)% rMOD[MOD];
        x = (x*x) % rMOD[MOD];
        pow >>= 1;
    }

    return res;
}

ll solve(ll n) {
    find_rMod(MOD);

    Mat base(2, 1);
    Mat func(2, 2);
    base.v[0][0] = 10%MOD;
    base.v[1][0] = 2%MOD;

    func.v[0][0] = 10%MOD;
    func.v[0][1] = -1;
    func.v[1][0] = 1;
    func.v[1][1] = 0;

    ll rfuncp = ll_pow(2, n);
    Mat rfunc = mat_pow(func, rfuncp);
    base = rfunc*base;
    return ((base.v[0][0])%MOD - 1 + MOD)%MOD;
}

int main() {
    // freopen("input.txt", "r", stdin);
    memset(rMOD, -1, sizeof(rMOD));
    ll n;
    int ncase;
    scanf("%d", &ncase);
    for(int t = 1; t <= ncase; ++t) {
        scanf("%lld%lld", &n, &MOD);
        printf("Case #%d: %lld\n", t, solve(n));
    }
}