关于我与我的神奇代码
  • 板块灌水区
  • 楼主正方体很方
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/11/23 21:35
  • 上次更新2023/11/5 07:26:42
查看原帖
关于我与我的神奇代码
205281
正方体很方楼主2020/11/23 21:35

P1962 斐波那契数列 这是代码:

#include<ctime>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const long long mod=1000000007;
struct mat
{
	long long a[5][5];
}f,ans;

mat X(mat x,mat y)
{
	mat z;
	long long i,j,l;
	for(i=1;i<=2;i++)
	  for(j=1;j<=2;j++)
	    z.a[i][j]=0;
	
	for(i=1;i<=2;i++)
	  for(j=1;j<=2;j++)
	    for(l=1;l<=2;l++)
	      z.a[i][j]=((x.a[i][l]*y.a[l][j])%mod+z.a[i][j])%mod;
	      
	return z;
}
mat ksm(long long k)
{
	mat an;
	long long i,j;
	for(i=1;i<=2;i++)
	  for(j=1;j<=2;j++) 
	    an.a[i][j]=0;
	for(i=1;i<=2;i++)
	  an.a[i][i]=1;
	
	while(k)
	{
		if(k&1)
		  an=X(an,f);
		k=k>>1;
		f=X(f,f);
	}
	return an;	
}

int main()
{
	long long m;
	
	scanf("%lld",&m);
		
	f.a[1][1]=1;f.a[1][2]=1;
	f.a[2][1]=1;f.a[2][2]=0;
        
	if(m<=2) 
	{
		printf("1\n");return 0; 
	}
	for(int j=1;j<=2;j++)
	    for(int k=1;k<=2;k++) 
	        ans.a[j][k]=0;
	    
	ans=ksm(m-2);
	long long h=0;
	for(int j=1;j<=3;j++)
	    h+=ans.a[1][j];
	h=(h%mod+mod)%mod;
	    
	printf("%lld\n",h);
	
	return 0;
}

连续提交5次,分数在30~60不等,而且每次WA的点都不一样

有大佬能解释一下吗?

2020/11/23 21:35
加载中...