点击此处即可传送HIT 2060
As we know , the Fibonacci numbers are defined as follows: F(n) == {1 n==0||n==1{F(n-1)+F(n-2) n>1;Given two numbers a and b , calculate . 从a到b之间的斐波那契数的和Input The input contains several test cases. Each test case consists of two non-negative integer numbers a and b (0 ≤ a ≤ b ≤1,000,000,000). Input is terminated by a = b = 0. Output For each test case, output S mod 1,000,000,000, since S may be quite large. Sample Input Sample Output
题目大意：就是给你一个a和b，， 求从a到b之间的斐波那契数的和
解题思路：矩阵乘法，注意考虑边界条件： 具体详见代码： 上代码：
/*2015 – 8 – 14 上午Author: ITAK今日的我要超越昨日的我，明日的我要胜过今日的我，以创作出更好的代码为目标，不断地超越自己。using namespace std;const int maxn = 3;typedef long long LL;const int mod = 1e9;typedef struct{LL m[maxn][maxn];} Matrix;Matrix P = {1,1,0,1,0,0,1,1,1,};Matrix I = {1,0,0,0,1,0,0,0,1,};Matrix matrix_mul(Matrix a, Matrix b){int i, j, k;Matrix c;for(i=0; i<maxn; i++){for(j=0; j<maxn; j++){c.m[i][j] = 0;for(k=0; k<maxn; k++)c.m[i][j] += (a.m[i][k] * b.m[k][j]) % mod;c.m[i][j] %= mod;}}return c;}Matrix quick_mod(LL m){Matrix ans = I, b = P;while(m){if(m & 1)ans = matrix_mul(ans, b);m >>= 1;b = matrix_mul(b, b);}return ans;}int main(){LL a, b;while(~scanf(“%lld%lld”,&a,&b)){Matrix tmp1, tmp2;if(!a && !b)break;if(a == 0){if(b == 1)puts(“2”);else{tmp2 = quick_mod(b-1);LL ans2 = tmp2.m[2][0]+tmp2.m[2][1]+2*tmp2.m[2][2];LL ans = (ans2%mod-1)%mod;if(ans < 0)ans += mod;printf(“%lld\n”,ans+1);}}else if(a == 1){if(b == 1)puts(“1”);else{tmp2 = quick_mod(b-1);LL ans2 = tmp2.m[2][0]+tmp2.m[2][1]+2*tmp2.m[2][2];LL ans = (ans2%mod-1)%mod;if(ans < 0)ans += mod;printf(“%lld\n”,ans);}}else{tmp1 = quick_mod(a-2);tmp2 = quick_mod(b-1);LL ans1 = tmp1.m[2][0]+tmp1.m[2][1]+2*tmp1.m[2][2];LL ans2 = tmp2.m[2][0]+tmp2.m[2][1]+2*tmp2.m[2][2];//cout<<ans1 << ” “<<ans2<<” “;LL ans = (ans2%mod – ans1%mod);if(ans < 0)ans += mod;printf(“%lld\n”,ans);}}return 0;}
但是至少可以为自己的荷包省钱可以支些招，这点还是很现实的。
