HDU-2802-F(N)

看到这题讨论版里有说用公式的有说用循环节的，但是个人觉得这两种方法都不靠谱，比赛场上做这种题能直接推出公式需要很强数学功底，而循环节的方法如果循环节比较大就不太好发现了。这种已知通项公式的题还是用矩阵快速幂比较通用，但同是矩阵快速幂，对于这题，也有很大的差异；

注：memmove这个函数可能不太常见，但还是比较好用的，可以用较低的时间复杂度完成数组的拷贝

方法一

Time Limit Exceeded

2802

1000MS

1348K

1734 B

G++

#include "bits/stdc++.h"

using namespace std;

const int MOD = ;

/*

 {f(n - 1), f(n - 2), n ^ 3, (n - 1) ^ 3, n ^ 2, n, 1}

 乘MAT得到

 {f(n), f(n - 1), (n + 1) ^ 3, n ^ 3, (n + 1) ^ 2, n + 1, 1}

*/

const int MAT[][] = {

    {, , , -, , , },

    {, , , , , , },

    {, , , , , , },

    {, , , , , , },

    {, , , , , , },

    {, , , , , , },

    {, , , , , , }

};

const int TABLE[] = {, , , , , , };

struct Mat {

    int mat[][];

    Mat() {

        memset(mat, , sizeof(mat));

    }

    friend Mat operator * (Mat n, Mat m) {

        Mat res;

        for (int k = ; k < ; k++)

        for (int i = ; i < ; i++)

        for (int j = ; j < ; j++) {

            res.mat[i][j] += n.mat[i][k] * m.mat[k][j];

            // 因为当n >=0 时 (n + 1) ^ 3 一定大于 n ^ 3,所以要保证结果是正数;

            res.mat[i][j] = (res.mat[i][j] % MOD + MOD) % MOD;

        }

        return res;

    }

} m;

Mat mat_pow(Mat n, int k) {

    Mat res;

    for (int i = ; i < ; i++) {

        res.mat[i][i] = ;

    }

    while (k) {

        if (k & ) {

            res = res * n;

        }

        n = n * n;

        k >>= ;

    }

    return res;

}

int main() {

    int n;

    while (scanf("%d", &n) && n) {

        if (n == ) {

            puts("");

            continue;

        }

        if (n == ) {

            puts("");

            continue;

        }

        memmove(m.mat, MAT, sizeof(m.mat));

        m = mat_pow(m, n - );

        int res = ;

        for (int i = ; i < ; i++) {

            res = (res + m.mat[][i] * TABLE[i]) % MOD;

        }

        printf("%d\n", res);

    }

    return ;

}

这是拿到题直接把递推式拿来套的解法，7层矩阵，超时。于是想到n ^ 3 - (n - 1) ^ 3 = (n - 1) ^ 3 + 3 * (n - 1) ^ 2 + 3 * (n - 1) + 1 - (n - 1) ^ 3;可以抵消(n - 1) ^ 3;

方法二

Accepted

2802

889MS

1384K

1462 B

G++

#include "bits/stdc++.h"

using namespace std;

const int MOD = ;

/*

 {f(n - 1), f(n - 2), n ^ 2, n, 1}

 乘MAT得到

 {f(n), f(n - 1), (n + 1) ^ 2, n + 1, 1}

*/

const int MAT[][] = {

    {, , , , },

    {, , , , },

    {, , , , },

    {, , , , },

    {, , , , }

};

const int TABLE[] = {, , , , };

struct Mat {

    int mat[][];

    Mat() {

        memset(mat, , sizeof(mat));

    }

    friend Mat operator * (Mat n, Mat m) {

        Mat res;

        for (int k = ; k < ; k++)

        for (int i = ; i < ; i++)

        for (int j = ; j < ; j++)

        res.mat[i][j] = (res.mat[i][j] + n.mat[i][k] * m.mat[k][j]) % MOD;

        return res;

    }

} m;

Mat mat_pow(Mat n, int k) {

    Mat res;

    for (int i = ; i < ; i++) {

        res.mat[i][i] = ;

    }

    while (k) {

        if (k & ) {

            res = res * n;

        }

        n = n * n;

        k >>= ;

    }

    return res;

}

int main() {

    int n;

    while (scanf("%d", &n) && n) {

        if (n == ) {

            puts("");

            continue;

        }

        if (n == ) {

            puts("");

            continue;

        }

        memmove(m.mat, MAT, sizeof(m.mat));

        m = mat_pow(m, n - );

        int res = ;

        for (int i = ; i < ; i++) {

            res = (res + m.mat[][i] * TABLE[i]) % MOD;

        }

        printf("%d\n", res);

    }

    return ;

}

降到5层矩阵之后能AC掉这题了，但是这个矩阵还不是最好的。这个代码的效率还是不高。

方法三

Accepted

2802

483MS

1392K

1551 B

G++

#include "bits/stdc++.h"

using namespace std;

const int MOD = ;

/*

 {f(n - 2), (n + 1) ^ 2, (n + 1), 1}

 乘MAT得到

 {f(n), (n + 3) ^ 2, n + 3, 1}

*/

const int MAT[][] = {

    {, , , },

    {, , , },

    {, , , },

    {, , , }

};

const int TABLE1[] = {, , , };

const int TABLE2[] = {, , , };

struct Mat {

    int mat[][];

    Mat() {

        memset(mat, , sizeof(mat));

    }

    friend Mat operator * (Mat n, Mat m) {

        Mat res;

        for (int k = ; k < ; k++)

        for (int i = ; i < ; i++)

        for (int j = ; j < ; j++)

        res.mat[i][j] = (res.mat[i][j] + n.mat[i][k] * m.mat[k][j]) % MOD;

        return res;

    }

} m;

Mat mat_pow(Mat n, int k) {

    Mat res;

    for (int i = ; i < ; i++) {

        res.mat[i][i] = ;

    }

    while (k) {

        if (k & ) {

            res = res * n;

        }

        n = n * n;

        k >>= ;

    }

    return res;

}

int main() {

    int n;

    while (scanf("%d", &n) && n) {

        if (n == ) {

            puts("");

            continue;

        }

        if (n == ) {

            puts("");

            continue;

        }

        memmove(m.mat, MAT, sizeof(m.mat));

        m = mat_pow(m, n -  >> );

        int res = ;

        /*

          假设重定义两个函数，a(n) = f(2 * n - 1), b(n) = f(2 * n);

          if (n & 1) 求得a((n - 1) >> 1)即为 f(n)

          else 求得b((n - 1) >> 1) 即为f(n)

        */

        if (n & ) {

            for (int i = ; i < ; i++) {

                res = (res + m.mat[][i] * TABLE1[i]) % MOD;

            }

        } else {

            for (int i = ; i < ; i++) {

                res = (res + m.mat[][i] * TABLE2[i]) % MOD;

            }

        }

        printf("%d\n", res);

    }

    return ;

}

递推式是从f(n)直接到f(n + 2)的，所以相当于把f拆成两个函数分开讨论，只用4层矩阵就够了。对于矩阵快速幂，4层应该是最少的了。如果还要再快，那就只能采取循环节或公式的方式了。

方法四(来自讨论版，代码省略)

这题的循环节是4018(正好是MOD的两倍，不知道是不是巧合)。

方法五(来自讨论版，代码省略)

n为奇数 （n+1）(n+1)(2n-1)/4;

n为偶数 n*n*(2n+3)/4

巴特西

HDU-2802-F(N)

最新文章

热门文章