C - Recursive sequence （矩阵快速幂）

淡淡的烟草味﹌ 2023-06-17 13:58 4阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。

复现的时候一直在推矩阵快速幂的矩阵，可是一直都推不出来。后面才发现我这个sb。把（n+1）^4 的展开写错了。导致，没找到矩阵。其实这个题，本质上很简单，找到（n+1）^4 和n之间的规律就可以写出来了。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    const ll mod = 2147493647;
    const int N=7;
    
    int T;
    ll k,n,m;
    ll tmp[N][N];
    
    void multi(ll a[][N],ll b[][N],ll n)
    { 
        memset(tmp,0,sizeof tmp);
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                for(int k=0; k<n; k++)
                    tmp[i][j]+=((a[i][k] % mod)*(b[k][j] % mod)) % mod;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                a[i][j]=tmp[i][j];
    }
    ll res[N][N];
    void Pow(ll a[][N],ll n)
    { 
        memset(res,0,sizeof res);//n是幂，N是矩阵大小
        for(int i=0; i<N; i++)
            res[i][i]=1;
        while(n)
        { 
            if(n&1)
                multi(res,a,N);//res=res*a;复制直接在multi里面实现了；
            multi(a,a,N);//a=a*a
            n>>=1;
        }
    }
    
    ll a[N][N];
    void init()
    { 
        memset(a,0,sizeof(a));
        a[0][0] = 1; a[0][1] = 2; a[0][2] = 1;
        a[1][0] = 1;
        a[2][2] = 1; a[2][3] = 4; a[2][4] = 6; a[2][5] = 4; a[2][6] = 1;
        a[3][3] = 1; a[3][4] = 3; a[3][5] = 3; a[3][6] = 1;
        a[4][4] = 1; a[4][5] = 2; a[4][6] = 1;
        a[5][5] = 1; a[5][6] = 1;
        a[6][6] = 1;
    }
    
    int main()
    { 
        scanf("%d",&T);
        while(T --)
        { 
            scanf("%lld%lld%lld",&k,&n,&m);
            if(k <= 2)
            { 
                if(k == 1) printf("%lld\n",n);
                else printf("%lld\n",m);
                continue;
            }
            init();
            Pow(a,k - 2);
            ll ans = 0;
            ans = ans + res[0][0] * m % mod; ans %= mod;
            ans = ans + res[0][1] * n % mod; ans %= mod;
            ans = ans + res[0][2] * 81 % mod; ans %= mod;
            ans = ans + res[0][3] * 27 % mod; ans %= mod;
            ans = ans + res[0][4] * 9 % mod; ans %= mod;
            ans = ans + res[0][5] * 3 % mod; ans %= mod;
            ans = ans + res[0][6] % mod; ans %= mod;
            printf("%lld\n",ans);
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/