DUTacm 1085 Water Problem(矩阵快速幂 找规律)

DUTacm 1085连接

题目大意

已知 f(1)，f(2) 的值,且对于任意 x>1 ,有 f(x+1)=f(x)+f(x−1)+sin(πx2) ,求 f(n) 的值

分析

找规律之后可以发现这样的式子:

f(n)=fib(n−2)∗f(1)+fib(n−1)∗f(2)+C(n)

C(n)={−fib(n/2−1)∗fib(n/2−1),−fib(n/2)∗fib(n/2−1),n%2==0n%2==1 由于n比较大，斐波那契数需要用矩阵快速幂来求，参考: 【模板】矩阵快速幂求斐波那契

总结

这道题WA好多次，总结以下需要注意的地方 1.对于模运算中出现了减法运算的需要对结果再加一个MOD数再取模,形如: ((a−b)%MOD)+MOD)%MOD; 2.注意哪些地方可能会出现加爆的情况一定要取模 3.一个很有用的Bebug技巧是利用评测系统的返回结果来判断自己程序可能出现的错误，比如我想知道我的答案是否有负数的情况，在程序里面当答案出现负数的时候就运行死循环，评测结果如果是TLE那就说明是负数的原因了。 4.由于这道题数据比较大，虽然题目要求数据范围是 109 但在斐波那契的过程中有乘法可能会乘爆，所以要用long long int

代码

#include<cstdio> #include<iostream> #include<cstring> #include<cmath> const int MOD=1000000007; using namespace std; typedef long long int LL; LL f1,f2,n; struct Matrix { LL m[2][2]; }; Matrix Mul(Matrix a,Matrix b)//两个矩阵相乘 { Matrix c; memset(c.m,0,sizeof(c.m)); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) c.m[i][j]+=((a.m[i][k]*b.m[k][j])%MOD+MOD)%MOD; return c; } Matrix Fastm(Matrix a,int n)//求矩阵a的n次幂 { Matrix res; memset(res.m,0,sizeof(res.m)); res.m[0][0]=res.m[1][1]=1;//初始化res为单位矩阵 while(n) { if(n&1)//如果为奇数 res=Mul(res,a); n>>=1; a=Mul(a,a); } return res; } LL fib(LL x)//求fib[x]结果取模MOD { if(x==1 || x==2)return 1; Matrix ans; memset(ans.m,0,sizeof(ans.m)); ans.m[0][0]=ans.m[0][1]=ans.m[1][0]=1; ans=Fastm(ans,x-2); return ((ans.m[0][0]*1+ans.m[0][1]*1)%MOD+MOD)%MOD; } void Timeout() { while(1){} } void Work() { if(n==1){cout<<f1<<endl;return ;} else if(n==2){cout<<f2<<endl;return ;} else if(n==3){cout<<(f1+f2)%MOD<<endl;return ;}//注意f1+f2也需要取模 LL ans=0; ans+=((fib(n-1)*f2)%MOD+(fib(n-2)*f1)%MOD)%MOD; if(n%2==0)ans=((ans-(fib(n/2-1)*fib(n/2-1))%MOD)+MOD)%MOD; else ans=((ans-(fib(n/2)*fib(n/2-1))%MOD)+MOD)%MOD; //if(ans<0 || ans>MOD)Timeout();//测试的时候可以这样判断答案是否越界 cout<<ans<<endl; } int main() { while(scanf("%lld%lld%lld",&f1,&f2,&n)!=EOF) { Work(); } return 0; }