http://lx.lanqiao.org/problem.page?gpid=T121
如有错误,欢迎指出,讨论~
蓝桥杯里面的数据相当水...很容易就能够水过去现场思路
首先...
我们有矩阵快乘的方式可以O(logn)求出Fib[n]%mod
我的实现略有不同,本质一样
矩阵乘法之中会出现Ω(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;
}