【打表找规律+矩阵快速幂】number number number HDU - 6198

谁借莪１个温暖的怀抱￠ 2022-06-08 02:07 181阅读 0赞

Think:  
1知识点：打表找规律+矩阵快速幂  
2题意：给定一个数n，若可以从斐波那契数列中寻找不超过k个数(可重发选择)使得这k个数的累加和为n，则称n为mjf−good，若找不到不超过k个数(可重复选择)使得这k个数的累加和为n，则称n为mjf−bad，输入k(1≤k≤109)，输出最小的mjf\_bad modulo 998244353。  
3方法：  
1>打表找规律，发现F\[k\] = f\[2\*(k+1)+1\] - 1  
2>k太大，通过矩阵快速幂求解斐波那契数列第n项  
![这里写图片描述][SouthEast]  
[矩阵快速幂求解斐波那契数列——建议参考博客][Link 1]  
4反思：  
1>矩阵乘法注意不要爆int  
2>矩阵乘法注意及时取模

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——矩阵乘法时爆int导致运算错误

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int mod = 998244353;
    
    struct Matrix{
        int v[4][4];
    };
    
    Matrix multiply(Matrix x, Matrix y, int Matrix_len);
    Matrix matrix_pow(Matrix a, int k, int Matrix_len);
    
    int main(){
        int k, kk, ans;
        Matrix x, y, z;
        while(~scanf("%d", &k)){
            x.v[0][0] = 1, x.v[0][1] = 1, x.v[1][0] = 1, x.v[1][1] = 0;
            y.v[0][0] = 1, y.v[0][1] = 0, y.v[1][0] = 0, y.v[1][1] = 0;
    
            kk = 2*(k+1)+1;
            x = matrix_pow(x, kk-1, 2);
            z = multiply(x, y, 2);
    
            ans = (z.v[0][0]-1+mod) % mod;
            printf("%d\n", ans);
        }
        return 0;
    }
    Matrix multiply(Matrix x, Matrix y, int Matrix_len){
        Matrix z;
        memset(z.v, 0, sizeof(z.v));
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                for(int k = 0; k < Matrix_len; k++){
                    z.v[i][j] += x.v[i][k] * y.v[k][j];
                    z.v[i][j] %= mod;
                }
            }
        }
        return z;
    }
    Matrix matrix_pow(Matrix a, int k, int Matrix_len){
        Matrix b;
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                i == j? b.v[i][j] = 1: b.v[i][j] = 0;
            }
        }
        while(k){
            if(k & 1)
                b = multiply(b, a, 2);
            a = multiply(a, a, 2);
            k >>= 1;
        }
        return b;
    }

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const int mod = 998244353;
    
    struct Matrix{
        LL v[4][4];
    };
    
    Matrix multiply(Matrix x, Matrix y, int Matrix_len);/*矩阵乘法*/
    Matrix matrix_pow(Matrix a, int k, int Matrix_len);/*矩阵快速幂*/
    
    int main(){
        LL k, kk, ans;
        Matrix x, y, z;
        while(~scanf("%lld", &k)){
            x.v[0][0] = 1, x.v[0][1] = 1, x.v[1][0] = 1, x.v[1][1] = 0;
            y.v[0][0] = 1, y.v[0][1] = 0, y.v[1][0] = 0, y.v[1][1] = 0;
    
            kk = 2*(k+1)+1;
            x = matrix_pow(x, kk-1, 2);
            z = multiply(x, y, 2);
    
            ans = (z.v[0][0]-1+mod) % mod;
            printf("%lld\n", ans);
        }
        return 0;
    }
    Matrix multiply(Matrix x, Matrix y, int Matrix_len){
        Matrix z;
        memset(z.v, 0, sizeof(z.v));
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                for(int k = 0; k < Matrix_len; k++){
                    z.v[i][j] += x.v[i][k] * y.v[k][j];
                    z.v[i][j] %= mod;
                }
            }
        }
        return z;
    }
    Matrix matrix_pow(Matrix a, int k, int Matrix_len){
        Matrix b;
        for(int i = 0; i < Matrix_len; i++){
            for(int j = 0; j < Matrix_len; j++){
                i == j? b.v[i][j] = 1: b.v[i][j] = 0;
            }
        }
        while(k){
            if(k & 1)
                b = multiply(b, a, 2);
            a = multiply(a, a, 2);
            k >>= 1;
        }
        return b;
    }

[SouthEast]: /images/20220608/dadf00d8c7924c22ad5d0782f9bdd77c.png
[Link 1]: http://blog.csdn.net/nyist_tc_lyq/article/details/52981353
[vjudge]: https://vjudge.net/problem/HDU-6198