1038 递推 矩阵乘法 快速幂


链接:https://ac.nowcoder.com/acm/contest/26656/1038
来源:牛客网

题目描述

JYM和XJ转眼就从小学上了高中。在学习递推的时候,JYM在纸上随手写了一个递推关系式:an=2*an-1,a0=0。写完这个递推式,JYM拿给XJ看,XJ觉得太过简单,于是大笔一挥,在等式右边又加了一个式子,变成了这样:an=2*an-1+n2。JYM看到这个式子,想要算几个项来看看,可是一算就发现这个数据量太大了,你能帮他解决这个问题吗?

输入描述:

输入数据有多组(不超过100组数据),每组数据包含一个整数N<=10

18

输出描述:

一个整数X,表示递推式第n项的值。由于数字太大,因此结果对于1000000009取模后输出。

示例1

输入

复制

0
1
2
3

输出

复制

0
1
6
21

 

分析

就是想用结构体搞,结果好难。

ans数组还是直接弄成列的形式吧,以后不用搞混了。

1038	递推 矩阵乘法 快速幂

 

 

//-------------------------代码----------------------------

#define int ll
const ll mod = 1e9 + 9;

struct Node {
    ll a[4][4] = {
        {2,1,0,0},
        {0,1,2,1},
        {0,0,1,1},
        {0,0,0,1}
    };
    Node operator* (Node b) {
        Node x;
        ms(x.a,0);
        for(int i = 0;i<4;i++) {
            for(int j = 0;j<4;j++) {
                for(int k = 0;k<4;k++) {
                    x.a[i][j] = x.a[i][j] % mod + this->a[i][k] * b.a[k][j] % mod;
                    x.a[i][j] %= mod;
                }
            }
        }
        return x;
    }
};

Node quick(Node a,ll ans) {
    if(ans == 1) {
        return a;
    }
    Node x;
    ans -- ;
    while( ans ) {
        if( ans & 1 ) {
            x = x * a;
        }
        a = a * a ;
        ans >>= 1;
    }
    return x;
}

void solve(int n)
{
    if(n == 0 ) {
        cout<<0<<endl;
        return;
    }
    Node a;
    a = quick(a, n);

    Node f;
    ms(f.a,0);
    f.a[0][0] = 0;
    f.a[1][0] = 1;
    f.a[2][0] = 1;
    f.a[3][0] = 1;
    f = a * f ;
    ll fin = (f.a[0][0]) % mod;
//     dbb(f.a[0][0],f.a[1][0]);
    cout<<fin<<endl;
}

signed main(){
    clapping();TLE;

    ll n;
//    int t;cin>>t;while(t -- )
//     while(cin>>n)
    while(cin>>n)
        solve(n);
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/278000.html

(0)
上一篇 2022年7月31日
下一篇 2022年7月31日

相关推荐

发表回复

登录后才能评论