必赢的网址登录 > 必赢 > 一个整数 n,一个整数 n

原标题:一个整数 n,一个整数 n

浏览次数:194 时间:2019-09-25

主题材料背景

大家都精晓,斐波那契数列是满意如下性质的八个数列:

• f = 1

• f = 1

• f = f + f (n ≥ 2 且 n 为整数)

洛谷P一九六一 斐波那契数列,p1961斐波这契数列

洛谷P一九六一 斐波那契数列,p一九六五斐波那契数列

主题素材汇报

请你求出 f mod 一千000007 的值。

主题素材背景

世家都知晓,斐波那契数列是满意如下性质的一个数列:

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

主题素材背景

世家都晓得,斐波这契数列是满意如下性质的多个数列:

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

输入输出格式

输入格式:

·第 1 行:二个大背头 n

输出格式:

第 1 行: f mod 1000000007 的值

一个整数 n,一个整数 n。主题素材陈述

请你求出 f(n) mod 一千000007 的值。

标题汇报

请你求出 f(n) mod 一千000007 的值。

输入输出样例

输入样例#1:复制

5

输出样例#1:复制

5

输入样例#2:复制

10

出口样例#2:复制

55

输入输出格式

输入格式:

 

·第 1 行:三个整数 n

 

输出格式:

 

第 1 行: f(n) mod 1000000007 的值

 

输入输出格式

输入格式:

 

·第 1 行:一个寸头 n

 

出口格式:

 

第 1 行: f(n) mod 1000000007 的值

 

说明

对于 60% 的数据: n ≤ 92

对于 100% 的数据: n在long long范围内。

感觉温馨学的直白是假的矩阵连忙幂。。。

扶植矩阵为

$begin{bmatrix} 0 & 1 \ 1 & 1 end{bmatrix}$

#include<cstdio>#include<cstring>#define int long long #define getchar() (p1==p2&&(p2=+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)using namespace std;const int MAXN=101;const int mod=1e9+7;char buf[1<<20],*p1=buf,*p2=buf;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,k;struct Matrix{    int m[MAXN][MAXN];    Matrix operator * (const Matrix a)const    {        Matrix ans={};        for(int k=1;k<=n;k++)            for(int i=1;i<=n;i++)                for(int j=1;j<=n;j++)                    ans.m[i][j]=(ans.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;        return ans;    }            Matrix pow(int p)    {        Matrix ans,a=(*this);        for(int i=1;i<=n;i++) ans.m[i][i]=1;        while        {            if(p&1) ans=ans*a;            a=a*a;        //    a.print();            p>>=1;        }        return ans;    }    void print()    {        for(int i=1;i<=n;i++,puts(""))            for(int j=1;j<=n;j++)                printf("%d ",m[i][j]);        printf("*******************n");    }};main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #endif    k=read();n=2;    Matrix temp,ans;    temp.m[1][1]=0;temp.m[1][2]=1;    temp.m[2][1]=1;temp.m[2][2]=1;    ans.m[1][1]=0;ans.m[1][2]=1;    ans.m[2][1]=0;ans.m[2][2]=1;    temp=temp.pow;    ans=ans*temp;    printf("%d",ans.m[1][1]);    return 0;}

输入输出样例

输入样例#1: 复制

5

输出样例#1: 复制

5

输入样例#2: 复制

10

出口样例#2: 复制

55

输入输出样例

输入样例#1: 复制

5

输出样例#1: 复制

5

输入样例#2: 复制

10

输出样例#2: 复制

55

说明

对于 60% 的数据: n ≤ 92

对于 100% 的数据: n在long long(INT64)范围内。

 

倍感温馨学的直白是假的矩阵火速幂。。。

救助矩阵为

$begin{bmatrix} 0 & 1 \ 1 & 1 end{bmatrix}$

 

 

#include<cstdio>
#include<cstring>
#define int long long 
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int MAXN=101;
const int mod=1e9+7;
char buf[1<<20],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,k;
struct Matrix
{
    int m[MAXN][MAXN];
    Matrix operator * (const Matrix a)const
    {
        Matrix ans={};
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    ans.m[i][j]=(ans.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;
        return ans;
    }        
    Matrix pow(int p)
    {
        Matrix ans,a=(*this);
        for(int i=1;i<=n;i++) ans.m[i][i]=1;
        while(p)
        {
            if(p&1) ans=ans*a;
            a=a*a;
        //    a.print();
            p>>=1;
        }
        return ans;
    }
    void print()
    {
        for(int i=1;i<=n;i++,puts(""))
            for(int j=1;j<=n;j++)
                printf("%d ",m[i][j]);
        printf("*******************n");
    }
};
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    k=read();n=2;
    Matrix temp,ans;
    temp.m[1][1]=0;temp.m[1][2]=1;
    temp.m[2][1]=1;temp.m[2][2]=1;
    ans.m[1][1]=0;ans.m[1][2]=1;
    ans.m[2][1]=0;ans.m[2][2]=1;
    temp=temp.pow(k);
    ans=ans*temp;
    printf("%d",ans.m[1][1]);
    return 0;
}

 

斐波那契数列,p壹玖陆贰斐波那契数列 标题背景 大家都领悟,斐波那契数列是满意如下性质的三个数列: f(1) = 1 f(2) = 1 f(n) = f(n-1) +...

说明

对于 60% 的数据: n ≤ 92

对于 100% 的数据: n在long long(INT64)范围内。

 

 

裸的矩阵快速幂

亟待特判0,1二种情景

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL long long 
 6 using namespace std;
 7 const int MAXN=200000001;
 8 const int mod=1000000007;
 9 inline LL read()
10 {
11     char c=getchar();LL flag=1,x=0;
12     while(c<'0'||c>'9')    {if(c=='-')    flag=-1;c=getchar();}
13     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();    return x*flag;
14 }
15 LL n;
16 struct Matrix
17 {
18     LL a[5][5];
19     Matrix()
20     {
21         memset(a,0,sizeof(a));
22     }
23 };
24 Matrix Matrix_Mul(Matrix a,Matrix b)
25 {
26     Matrix c;
27     for(LL k=1;k<=2;k++)    
28         for(LL i=1;i<=2;i++)
29             for(LL j=1;j<=2;j++)
30                 c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;
31     return c;
32 }
33 inline void WORK()
34 {
35     Matrix bg,tmp;
36     bg.a[1][1]=1;bg.a[1][2]=1;
37     
38     tmp.a[1][1]=0;tmp.a[1][2]=1;
39     tmp.a[2][1]=1;tmp.a[2][2]=1;
40     while(n) 
41     { 
42         if(n&1)    bg=Matrix_Mul(bg,tmp);
43         tmp=Matrix_Mul(tmp,tmp);
44         n>>=1;
45     } 
46     printf("%lld",bg.a[1][2]%mod);
47 }
48 int main()
49 {
50     n=read();n=n-2;
51     if(n==-1||n==-2)    
52     {
53         printf("1");
54         return 0;
55     }
56         
57     
58     WORK();
59     return 0;
60 }

 

斐波那契数列,p壹玖陆伍斐波那契数列 标题背景 我们都知道,斐波那契数列是满意如下性质的二个数列: f(1) = 1 f(2) = 1 f(n) = f(n-1) +...

本文由必赢的网址登录发布于必赢,转载请注明出处:一个整数 n,一个整数 n

关键词:

上一篇:必赢的网址登录立即又起来新的2714历程,nginx 看

下一篇:没有了