首页 > 代码库 > AC日记——3的幂的和 51nod 1013

AC日记——3的幂的和 51nod 1013

3的幂的和

 

思路;

  矩阵快速幂;

    sn-1      3 1        sn

      *          =

  1      0 1     1

 

来,上代码:

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define mod 1000000007struct NodeType {    long long a[3][3];};struct NodeType ans;long long n;struct NodeType mul(NodeType pos){    NodeType res;    res.a[1][1]=0,res.a[1][2]=0;    res.a[2][1]=0,res.a[2][2]=0;    for(int i=1;i<=2;i++)    {        for(int j=1;j<=2;j++)        {            for(int v=1;v<=2;v++)            {                res.a[i][j]=(res.a[i][j]+(pos.a[i][v]*pos.a[v][j])%mod)%mod;            }        }    }    return res;}void poww(int mi){    NodeType pos;    pos.a[1][1]=3,pos.a[1][2]=1;    pos.a[2][1]=0,pos.a[2][2]=1;    while(mi>0)    {        struct NodeType res;        res.a[1][1]=0,res.a[1][2]=0;        res.a[2][1]=0,res.a[2][2]=0;        if(mi&1)        {            for(int i=1;i<=2;i++)            {                for(int j=1;j<=2;j++)                {                    for(int v=1;v<=2;v++)                    {                        res.a[i][j]=(res.a[i][j]+(ans.a[i][v]*pos.a[v][j])%mod)%mod;                    }                }            }            ans=res;        }        pos=mul(pos),mi=mi>>1;    }}int main(){    scanf("%lld",&n);n--;    ans.a[1][1]=3,ans.a[1][2]=1;    ans.a[2][1]=0,ans.a[2][2]=1;    poww(n);    cout<<(ans.a[1][1]+ans.a[1][2])%mod;    return 0;}

 

AC日记——3的幂的和 51nod 1013