1 条题解

  • 1
    @ 2017-10-20 21:15:30

    递推,30分
    #include<bits/stdc++.h>
    const long long maxn=2,mod=1e9+7;
    inline const void read(long long &a)
    {
    a=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
    a=(a<<1)+(a<<3)+c-'0';
    c=getchar();
    }
    }
    inline const void write(long long a)
    {
    if(a>9)write(a/10);
    putchar(a%10+'0');
    }
    int main()
    {
    long long n,p,k=0,a,f[2];
    read(n);
    f[0]=1;f[1]=2;
    k=1;
    for(long long i=3;i<=n;i++)
    {
    k^=1;
    a=f[k^1];
    f[k]=(f[k^1]+f[k])%mod;
    f[k^1]=a;
    }
    write(f[k]);
    return 0;
    }
    矩阵快速幂
    #include<bits/stdc++.h>
    const long long maxn=2,mod=1e9+7;
    inline const void read(long long &a)
    {
    a=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
    a=(a<<1)+(a<<3)+c-'0';
    c=getchar();
    }
    }
    inline const void write(long long a)
    {
    if(a>9)write(a/10);
    putchar(a%10+'0');
    }
    long long n;
    struct square
    {
    long long a[2][2];
    inline const void init(long long i,long long j,long long l,long long k)
    {
    a[0][0]=i;a[0][1]=j;
    a[1][0]=l;a[1][1]=k;
    }
    inline const void operator=(const square&b)
    {
    a[0][0]=b.a[0][0];
    a[0][1]=b.a[0][1];
    a[1][0]=b.a[1][0];
    a[1][1]=b.a[1][1];
    }
    inline const square operator*(square b)
    {
    square c;
    c.a[0][0]=(a[0][0]*b.a[0][0]%mod+a[0][1]*b.a[1][0]%mod)%mod;
    c.a[0][1]=(a[0][0]*b.a[0][1]%mod+a[0][1]*b.a[1][1]%mod)%mod;
    c.a[1][0]=(a[1][0]*b.a[0][0]%mod+a[1][1]*b.a[1][0]%mod)%mod;
    c.a[1][1]=(a[1][0]*b.a[0][1]%mod+a[1][1]*b.a[1][1]%mod)%mod;
    return c;
    }
    inline const void print()
    {
    write(a[0][0]);putchar(' ');write(a[0][1]);printf("\n");
    write(a[1][0]);putchar(' ');write(a[1][1]);printf("\n");
    }
    }f,p;
    const square fast_pow(square p,long long k)
    {
    square base,ans;
    base=p;
    ans.init(1,0,0,1);
    while(k)
    {
    if(k&1)ans=ans*base;
    k>>=1;
    base=base*base;
    }
    return ans;
    }
    int main()
    {
    read(n);
    f.init(1,2,0,0);p.init(0,1,1,1);
    f=f*fast_pow(p,n-2);
    write(f.a[0][1]%mod);
    return 0;
    }

  • 1

信息

难度
8
分类
(无)
标签
(无)
递交数
42
已通过
4
通过率
10%
上传者