hdu 3306 Another kind of Fibonacci

Another kind of Fibonacci

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1526 Accepted Submission(s): 583

Problem Description As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)2 +A(1)2+……+A(n)2.

Input There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 231 ? 1
X : 231? 1
Y : 231 ? 1

Output For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.
Sample Input

2 1 1 3 2 3

Sample Output

6 196

Author wyb
Source HDOJ Monthly Contest ? 2010.02.06
题解及代码:

#include #include #include using namespace std; const int mod=10007; struct mat { __int64 t[4][4]; void set() { memset(t,0,sizeof(t)); } } a,b; mat multiple(mat a,mat b,__int64 n,int p) { int i,j,k; mat temp; temp.set(); for(i=0; i>=1; b=multiple(b,b,n,p); } return t; } void init(__int64 x,__int64 y) { b.set(); b.t[0][0]=1; b.t[1][0]=x*x%mod;b.t[1][1]=x*x%mod;b.t[1][2]=x;b.t[1][3]=1; b.t[2][0]=2*x*y%mod;b.t[2][1]=2*x*y%mod;b.t[2][2]=y; b.t[3][0]=y*y%mod;b.t[3][1]=y*y%mod; } int main() { __int64 n,x,y; while(cin>>n>>x>>y) { x=x%mod; y=y%mod; init(x,y); a=quick_mod(b,4,n-1,mod); cout

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:UVA11549 Calculator Conundrum
下一篇:HDOJ 4883 TIANKENG’s restaurant
相关文章

Max Sum &&http://acm.hdu.edu.cn/s

hdu 1003 Max Sum

HDU 4007

hdu1856并查集

HDU2094

hdu 1089 Robotic Sort

hdu 1754

HDU 4028

http://acm.hdu.edu.cn/showproblem.p

HDU 4022

图文推荐
hdu 3306 Another kind of Fibonacci
ZOJ 3640 Help Me
hdu 3306 Another kind of Fibonacci
CF 518C(Anya and
hdu 3306 Another kind of Fibonacci
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-03 人气:12
本文关键词:
分享到:

相关文章

  • HDU 3306 Another kind of Fibonacci(矩阵快速幂) 2014-03-21

    题目地址:HDU 3306 没什么智商的题目,只要把构造矩阵硬算出来就行。 代码如下: #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int mod =1e4+7; struct matrix { int ma[5][5]; }init, res; matrix Mult(matrix x,

  • hdu 3326 Another kind of Fibonacci (矩阵构造) 2012-10-30

    题目大意: 描述了另外一种斐波那契 F[n] = x*F[n-1] + y*F[n-2]; 求segma(F[i]^2); 思路分析: 构造矩阵的详细 请戳我 构造矩阵可以得到 中间矩阵为 1 1 0 0 0 x^2 y^2 2*x*y 0 1 0 0 0 x 0 y #include #include #include #include #include #define N 30 typedef long long LL; using namespace std; const LL mod =

  • HDU3306Another kind of Fibonacci(简单矩阵快速幂) 2013-10-29

    哎,本来是想学学矩阵构造的方法的,,突然发现自己不用看直接就会yy构造。。。 看下右边有什么。。 题目地址:Another kind of Fibonacci AC代码: #include #include #include #include using namespace std; const int mod=10007; int p[4][4],a[4][4],tmp[4][4]; int n,x,y,ans[4],res[4]; void init() { int i,j; a[0][0]

  • HDU 4960 Another OCD Patient(记忆化搜索) 2015-03-12

    HDU 4960 Another OCD Patient 题目链接 记忆化搜索,由于每个碎片值都是正数,所以每个前缀和后缀都是递增的,就可以利用twopointer去找到每个相等的位置,然后下一个区间相当于一个子问题,用记忆化搜索即可,复杂度接近O(n^2) 代码: #include #include #include using namespace std; const int INF = 0x3f3f3f3f; const int N = 5005; typedef long long ll

  • HDU 4960 Another OCD Patient(区间dp记忆化搜索) 2012-03-09

    题目大意:给你一串数字让你判断经过若干次合并,使得这个数字串变成回文串的最小成本是多少。第一行是数字串,第二行是合并连续i个数字的成本是多少。 解题思路:区间dp,可以进行记忆化搜索,如果左边比右边和大那么右边一定是小了,右边比左边大那么左边一定小了。因为保证有解。具体不太好说,直接看代码吧。 Another OCD Patient Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

  • fzu 2038 Another Postman Problem(递归求解) 2014-03-25

    题目链接:fzu 2038 Another Postman Problem 题目大意:给出n, 然后给出n - 1条边,保证图联通,计算每个点到其他所有点的路径总和的和。 解题思路:一开始想到Floyd算法求出所有点点之间的最短路,但是o(n^3)的复杂度太高了;后来想到说用枚举起点后直接用BFS去计算距离,可是o(n^2)还是超时。后来灵光一闪,发现可以枚举每条边走过的次数,以为图肯定为无环图,所以剪断当前边后,可以将图上的点分为两个集合,然后走过的次数就是两个集合个数的乘积。然后递归遍历每个

  • poj1195--Mobile phones(二维树状数组) 2012-04-08

    Mobile phones Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 15182 Accepted: 7013 Description Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squa

  • RMQ (Range Minimum/Maximum Query)算法 2015-03-04

    1. 概述 RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j 2.RMQ算法 对于该问题,最容易想到的解决方案是遍历,复杂度是O(n)。但当数据量非常大且查询很频繁时,该算法无法在有效的时间内查询出正解。 本节介绍了一种比较高效的在线算法(ST算法)解决这个问题。所谓在线算法,是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理,待信息充足以后便可以用较少的时间回

  • HDU 4965 Fast Matrix Calculation(矩阵快速幂) 2013-10-13

    HDU 4965 Fast Matrix Calculation 题目链接 矩阵相乘为AxBxAxB...乘nn次,可以变成Ax(BxAxBxA...)xB,中间乘n n - 1次,这样中间的矩阵一个只有6x6,就可以用矩阵快速幂搞了 代码: #include #include const int N = 1005; const int M = 10; int n, m; int A[N][M], B[M][N], C[M][M], CC[N][N]; int ans[M][M]; void t

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.060 (s). 10 q(s)