2014蓝桥杯本科C/C++组预赛第9题<斐波那契>解题报告

首先是题目链接

http://lx.lanqiao.org/problem.page?gpid=T121

如有错误,欢迎指出,讨论~

蓝桥杯里面的数据相当水...很容易就能够水过去
现场思路
首先...
我们有矩阵快乘的方式可以O(logn)求出Fib[n]%mod
2014蓝桥杯本科C/C++组预赛第9题<斐波那契>解题报告

我的实现略有不同,本质一样
矩阵乘法之中会出现Ω(10^18)*Ω(10^18)%Ω(10^18)
直接乘法错误(比如 a=10^18-3,b=10^18-2,c=10^18-1,a*b%c直接写在程序里面导致结果错误)

这里需要用类似快速幂的做法

LL llmul( LL a,LL b,LL mod ) {
  a%=mod;a+=mod;a%=mod;
  b%=mod;b+=mod;b%=mod;
  if ( a<b )swap( a,b );
  LL ret=0;
  while ( b ) {
  if ( b&1 )ret=( ret+a )%mod;
  a=( a<<1 )%mod;
  b/=2;
  }
  return ret;
}

矩阵快速幂和这个的写法一样

这是解决Fib[n]%mod的函数们

struct matrix {
        LL x[3][3];
        matrix() {memset( x,0,sizeof x );}
};
matrix mmul( matrix &A,matrix &B,LL mod ) {
        matrix ret;
        for ( int i=1; i<=2; i++ )for ( int j=1; j<=2; j++ )for ( int k=1; k<=2; k++ )
                                ret.x[i][j]=( ret.x[i][j]+llmul( A.x[i][k],B.x[k][j],mod ) )%mod;
        return ret;
}
matrix E,A;
LL fib( LL n,LL mod ) {
        matrix O=E,B=A;
        while ( n ) {
                if ( n&1 )O=mmul( O,B,mod );
                B=mmul( B,B,mod );
                n/=2;
        }
        return O.x[1][2];
}

结论1 ∑{_1^n}Fib=Fib[n+2]-1

原问题等价于解决
Fib[n]%Fib[m]%mod
-1什么的,+2什么的别搞错了就行...
赛场上...对Fib[n]%Fib[m]%mod无计可施,有些思路但是走不到最后
由于2*mod需要小于long long的大小
所以m小于90的时候f[m]*2在long long内可存
这样能解决m<=89的所有情况
预处理出来

main中

	A.x[1][2]=A.x[2][1]=A.x[2][2]=1;
        E.x[1][1]=E.x[2][2]=1;
        int i,j;
        FIB[0]=0,FIB[1]=1;
        for(i=2;i<=89;i++)FIB[i]=FIB[i-1]+FIB[i-2];
        LL n,m,mod;
        while ( cin>>n>>m>>mod )
                cout<<( solve( n+2,m,mod )-1+mod )%mod<<endl;

显然当n<=m时fib[n]%fib[m]%mod很好解决

就有了下面的solve

LL solve( LL n,LL m,LL mod ){
        if(n<m)return fib(n,mod);
        if(n==m)return 0;
        if(m<=89)return fib(n,FIB[m])%mod;
        return -1;
}

然后我过了蓝桥里面的5个test(真够少的)......

=.=
比赛的时候这题干了几乎2h......
Orz

然后就去问人...

由于蓝桥数据过弱...不保证以下正确性...

请注意ab%c%d!=(a%c%d)*(b%c%d)%c%d
比如
[(2*3)%5]%3=1
(2%3)*(3%3)=0

首先有
结论2 F[n+k] = F[k]F[n+1] + F[k?1]F[n];
if n>m
F[n]=F[m+n-m]=F[m]F[n-m+1]+F[m-1]*F[n-m]
左右取%F[m]
F[n]%F[m]=F[m-1]*F[n-m]%F[m]
若仍有n-m>m可以继续这样处理
F[n]%F[m]=F[m-1]^([n/m])*F[n%m]%F[m]
记t=n/m向下取整
结论3 F[i+1]F[i?1] ? F[i]^2 = (?1)^i:
so f[i]^2%f[i+1]=(-1)^(i+1)
记 p=[t/2],q=t%2
so
Fib[n]%Fib[m]%mod
等价于
{ f[m-1]^q*(-1)^(pm)*f[n%m] }%f[m]%mod
如果q==0,那么很容易解决
记fuhao=(-1)^(pm)
原问题等价于
F[m-1]*F[n%m]*fuhao%f[m]%mod

结论4 x%y%mod=(x-[x/y]*y)*mod
记a=[x/y]
由于x=f[n%m]*f[m-1]
有这么一个炫酷的结论...
当m不太小的时候
f[n%m]*f[m-1]/f[m]
当n%m为奇数时是fib[n%m-1]
当n%m是偶数时是fiib[n%m-1]-1
就需要先处理下n%m==0的情况,这很简单=.=

=.=然后处理下符号的特殊情况
就是if fuhao<0 : a++
就是这样....


LL solve( LL n,LL m,LL mod ) {
	//f(n)%f(m)%mod
	LL t=n/m;
	//(f(m-1)^t*f(n%m))%f(m)%mod;
	//f(i)^2%f(i-1)=(-1)^(i+1)
	LL p=t/2,q=t%2;
	//{f(m-1)^q*(-1)^(pm)*f(n%m)}%f(m)%mod
	LL fuhao=p*m%2==0?1:-1;
	if ( q==0 ) {
		LL ans=fib( n%m,mod )*fuhao;
		ans%=mod;
		ans+=mod;
		return ans%mod;
	}
	if ( n%m==0 )return 0;
	//f(m-1)*f(n%m)*fuhao%f(m)%mod
	//x%y%mod=(x-a*y)%mod
	//a=[x/y]
	LL x=(llmul(fib(n%m,mod),fib(m-1,mod),mod)*fuhao%mod+mod)%mod;
	LL y=fib(m,mod);
	LL a=fib(n%m-1,mod);
	if(n%m%2==0)a--;
	if(fuhao<0)a++;
	a=(a%mod+mod)%mod;
	return ((x-llmul(a,y,mod))%mod+mod)%mod;
}


2014蓝桥杯本科C/C++组预赛第9题<斐波那契>解题报告,布布扣,bubuko.com

2014蓝桥杯本科C/C++组预赛第9题<斐波那契>解题报告

上一篇:JavaScript程序设计之常用窗口对象


下一篇:JAVA输入输出(IO)之文件