今天下午刚起来眼睛就比较涨,,而且还有点恶心,唉,结果一直不在状态,而且这个题太坑了。。。。 点击此处即可传送 Hit 2255
Maybe ACMers following series of numbers which you can guess is derived from the definition of fibonacci number. The definition of fibonacci number is: f(0) = 0, f(1) = 1, and for n>=2, f(n) = f(n – 1) + f(n – 2) We define the new series of numbers as below: f(0) = a, f(1) = b, and for n>=2, f(n) = p*f(n – 1) + q*f(n – 2),where p and q are integers. Just like , we are interested s-th element , to calculate .”””” Great!Let’s go! Input The a single test cases, followed by the input data for each test case. Each test case <= s <= e <= 2147483647. Output One line leading zeros should not be printed. Sample Input -Sample Output 23
题目大意: 就是给你好几个数,分别表示什么意思,看题就行了;
解题思路:矩阵乘法,递推公式,
注意了,注意了,千万不要用全局变量 if(ans < 0) ans += mod; printf(“%lld\n”,ans); } return 0; } !!!!!!!
/*2015 – 8 – 14 下午Author: ITAK今天非常非常的不顺心啊。。。。今日的我要超越昨日的我,明日的我要胜过今日的我,以创作出更好的代码为目标,,不断地超越自己。*/#include <iostream>#include <cstdio>using namespace std;const int maxn = 3;const int mod = 1e7;typedef long long LL;typedef struct{LL m[maxn][maxn];} Matrix;// LL a, b, s, e, q, p;千万不要用全局变量Matrix P = {0,0,0,1,0,0,0,0,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++){a.m[i][k] = (a.m[i][k]%mod + mod) % mod;b.m[k][j] = (b.m[k][j]%mod + mod) % mod;c.m[i][j] += (a.m[i][k] * b.m[k][j]) % mod;}c.m[i][j] = (c.m[i][j]%mod + mod) % 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(){int t;LL a, b, q, p, e, s;scanf(“%d”,&t);while(t–){Matrix tmp1, tmp2;LL ans, ans1, ans2;cin>>a>>b>>p>>q>>s>>e;P.m[0][0]=p;P.m[0][1]=q;P.m[2][0]=p;P.m[2][1]=q;if(s-2 > 0){tmp1 = quick_mod(s-2);ans1 = (b*tmp1.m[2][0])%mod + (a*tmp1.m[2][1])%mod + ((a+b)*tmp1.m[2][2])%mod;}else{if(s == 0)ans1 = 0;if(s == 1)ans1 = a;if(s == 2)ans1 = a + b ;}if(e-1 > 0){tmp2 = quick_mod(e-1);ans2 = (b*tmp2.m[2][0])%mod + (a*tmp2.m[2][1])%mod + ((a+b)*tmp2.m[2][2])%mod;}else{if(e == 0)ans2 = a;elseans2 = b+a;}ans1 = (ans1%mod+mod) % mod;ans2 = (ans2%mod+mod) % mod;//cout<<ans1<<” “<<ans2<<” “;ans = (ans2 – ans1 + mod) % mod;if(ans < 0)ans += mod;printf(“%lld\n”,ans);}return 0;}
如果我们想要更多的玫瑰花,就必须种植更多的玫瑰树。