正文

HDU 3306 Another kind of Fibonacci(矩阵+ll超时必须用int&输入必须取模&M必须是int类型)

IP云
IP云V管理员/4 阅读
08/05
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Another kind of Fibonacci

【题目链接】Another kind of Fibonacci

【题目类型】矩阵+ll超时必须用int&输入必须取模&M必须是int类型

&题解：

算出矩阵的每一行一定要和初始化的那个矩阵不一样,如果有一项是一样的,那么就推不出最后的答案,所以矩阵如下:



代码还有问题,T了,不知道为什么,明天在看吧

【时间复杂度】\(O(logn)\)

&超时代码：

#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int si= 6;
struct mat
{
ll m[si][si];
}A;
ll n,x,y,M=10007;
mat Mul(mat a,mat b)
{
mat c;
for(int i=0;i<si;i++)
for(int j=0;j<si;j++){
c.m[i][j]=0;
for(int k=0;k<si;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;
}
return c;
}
mat bPow(mat a,ll z)
{
mat un;
for(int i=0;i<si;i++)for(int j=0;j<si;j++)
un.m[i][j]=(i==j);
while(z){
if(z&1)
un=Mul(un,a);
a=Mul(a,a);
z>>=1;
}
return un;
}
ll tb[si];
void Init()
{
for(int i=0;i<5;i++)tb[i]=1;
tb[5]=2;
memset(A.m,0,sizeof(A.m));
A.m[0][0]=x,A.m[0][1]=y;
A.m[1][0]=1;
A.m[2][2]=x*x,A.m[2][3]=y*y,A.m[2][4]=2*x*y;
A.m[3][2]=1;
A.m[4][2]=x,A.m[4][4]=y;
for(int i=0;i<si;i++) A.m[5][i]=A.m[2][i];
A.m[5][5]=1;
}
void DF(mat a)
{
for(int i=0;i<si;i++){
for(int j=0;j<si;j++)
cout<<a.m[i][j]<<" ";
cout<<endl;
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
freopen("E:1.txt","r",stdin);
while(cin>>n>>x>>y){
x%=M,y%=M;
Init();
//DF(A);
ll ans=0;
if(n==0){
cout<<1<<endl;
}
else if(n==1){
cout<<2<<endl;
}
else{
A=bPow(A,n-1);
//DF(A);
for(int i=0;i<si;i++){
ans=(ans+A.m[5][i]*tb[i])%M;
}
cout<<ans<<endl;
}
}
return 0;
}

&题解2：

妈的,这题真tm智障,花了我2个小时,最后终于对照别人ac代码找到了错误.

注意1:矩阵中是long long 类型 运算没有int快 所以要改为int型 还有取模的M也必须要是int型 如果M是ll的话也会超时.

注意2:相应地,上面由long long改为int了 所以输入数据必须要取模了

总结:好智障的烂题啊,居然卡在数据类型上.(当然,也应该注意一下了:能用int的就不要用long long,因为如果用了long long 就有可能超时;原来一直以为用ll不会爆范围,就总是用ll,现在发现了,一直用ll会爆时间,尤其是在这种矩阵快速幂的题里,绝对要注意!!!)

&AC代码：

#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int si= 6;
struct mat
{
int m[si][si];
}A;
ll n,x,y;
int M=10007;
mat Mul(mat a,mat b)
{
mat c;
for(int i=0;i<si;i++)
for(int j=0;j<si;j++){
c.m[i][j]=0;
for(int k=0;k<si;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;
}
return c;
}
mat bPow(mat a,ll z)
{
mat un;
for(int i=0;i<si;i++)for(int j=0;j<si;j++)
un.m[i][j]=(i==j);
while(z){
if(z&1)
un=Mul(un,a);
a=Mul(a,a);
z>>=1;
}
return un;
}
ll tb[si];
void Init()
{
for(int i=0;i<5;i++)tb[i]=1;
tb[5]=2;
memset(A.m,0,sizeof(A.m));
A.m[0][0]=x,A.m[0][1]=y;
A.m[1][0]=1;
A.m[2][2]=x*x%M,A.m[2][3]=y*y%M,A.m[2][4]=2*x*y%M;
A.m[3][2]=1;
A.m[4][2]=x,A.m[4][4]=y;
for(int i=0;i<si;i++) A.m[5][i]=A.m[2][i];
A.m[5][5]=1;
}
void DF(mat a)
{
for(int i=0;i<si;i++){
for(int j=0;j<si;j++)
cout<<a.m[i][j]<<" ";
cout<<endl;
}
}
int main()
{
while(cin>>n>>x>>y){
x%=M,y%=M;
Init();
ll ans=0;
if(n==0){
cout<<1<<endl;
}
else if(n==1){
cout<<2<<endl;
}
else{
A=bPow(A,n-1);
for(int i=0;i<si;i++){
ans=(ans+A.m[5][i]*tb[i])%M;
}
cout<<ans<<endl;
}
}
return 0;
}

HDU 3306 Another kind of Fibonacci(矩阵+ll超时必须用int&输入必须取模&M必须是int类型)的更多相关文章

  1. hdu 3306 Another kind of Fibonacci 矩阵快速幂

    参考了某大佬的 我们可以根据(s[n-2], a[n-1]^2, a[n-1]*a[n-2], a[n-2]^2) * A = (s[n-1], a[n]^2, a[n]*a[n-1], a[n-1] ...

  2. HDU 3306 Another kind of Fibonacci ---构造矩阵&ast;&ast;&ast;

    Another kind of Fibonacci Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Jav ...

  3. hdu 3306 Another kind of Fibonacci（矩阵高速幂）

    Another kind of Fibonacci                                                        Time Limit: 3000/10 ...

  4. HDU 3306 Another kind of Fibonacci&lpar;快速幂矩阵&rpar;

    题目链接 构造矩阵 看的题解,剩下的就是模板了,好久没写过了,注意取余. #include <cstring> #include <cstdio> #include <s ...

  5. HDU 3306 - Another kind of Fibonacci

    给你 A(0) = 1 , A(1) = 1 , A(N) = X * A(N - 1) + Y * A(N - 2) (N >= 2). 求 S(N) = A(0) 2 +A(1) 2+……+ ...

  6. hdu 1097 A hard puzzle 快速幂取模

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1097 分析:简单题,快速幂取模, 由于只要求输出最后一位,所以开始就可以直接mod10. /*A ha ...

  7. hdu 1588（Fibonacci矩阵求和）

    题目的大意就是求等差数列对应的Fibonacci数值的和,容易知道Fibonacci对应的矩阵为[1,1,1,0],因为题目中f[0]=0,f[1]=1,所以推出最后结果f[n]=(A^n-1).a, ...

  8. POJ3070 Fibonacci&lbrack;矩阵乘法&rsqb;

    Fibonacci Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 13677   Accepted: 9697 Descri ...

  9. HDU 5895 Mathematician QSC&lpar;矩阵乘法&plus;循环节降幂&plus;除法取模小技巧&plus;快速幂&rpar;

    传送门:HDU 5895 Mathematician QSC 这是一篇很好的题解,我想讲的他基本都讲了http://blog.csdn.net/queuelovestack/article/detai ...

随机推荐

  1. Activiti系列：为什么Activiti 5&period;18 的REST的api总是返回404错误

    REST api可以访问了,如下 1.修改db.properties配置文件,让他访问sql server 2.在浏览器中输入如下地址,注意中间有一个service,这点和之前的不一样,在<Ac ...

  2. 使用Telerik的登陆模板实现DoubanFm的登陆&lpar;WP7&rpar;

    Telerik的控件很强大.我们直接使用其登陆模板. 在装过Telerik WP版后,就可以在VS里非常方便的添加页面了. 我们选择 Sign In Form 其XAML不是很长,直接贴出来 < ...

  3. android小知识之SparseArray&lpar;HaspMap替换&rpar;

    最近编程时,发现一个针对HashMap<Integer, E>的一个提示: 翻译过来就是:用SparseArray<E>来代替会有更好性能.那我们就来看看源码中SparseAr ...

  4. Android 真机无线调试

    有很多人在学Android的时候最开始接触的都是模拟机的测试,如果像好的模拟机比如genimotion,次一点的蓝手指,测试都还比较可以.有的也不缺乏是用真机测试.本人开始用华为真机测试,也是一直连线 ...

  5. CoreData和SQLite多线程访问时的线程安全问题

    数据库读取操作一般都是多线程访问的.在对数据进行读取时,我们要保证其当前状态不能被修改,即读取时加锁,否则就会出现数据错误混乱.IOS中常用的两种数据持久化存储方式:CoreData和SQLite,两 ...

  6. Android热修复技术选型——三大流派解析

    声明,本文转载自微信公众号文章 2015年以来,Android开发领域里对热修复技术的讨论和分享越来越多,同时也出现了一些不同的解决方案,如QQ空间补丁方案.阿里AndFix以及微信Tinker,它们 ...

  7. jsp篇 之 EL表达式

    EL表达式: 形式:${ } 作用:从一个[范围对象里面取值]或者从一个对象中取值或是向页面输出值. 之前我们使用<% ... %>等形式,并不够简洁. 例如: <% request ...

  8. SCOI2008着色方案&lpar;记忆化搜索&rpar;

    有n个木块排成一行,从左到右依次编号为1~n.你有k种颜色的油漆,其中第i 种颜色的油漆足够涂ci 个木块.所有油漆刚好足够涂满所有木块,即 c1+c2+...+ck=n.相邻两个木块涂相同色显得很难 ...

  9. AutoFac在MVC中的使用

    在asp.net mvc控制器中使用Autofac来解析依赖 如下Controller中使用构造函数依赖注入接口IUserService: public IUserService _IUserServ ...

  10. xe Style

    //注意引用:vcl.themes, vcl.styles, IOutils procedure TForm1.FormCreate(Sender: TObject); var stylename: ...