注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[HDU 4686]Arc of Dream  

2014-10-29 22:13:08|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Arc of Dream

题意很简单就不说了
想麻烦了QAQ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int MOD = 1E9+7;
typedef long long LL;
struct Matrix{
LL d[5][5];
Matrix(){memset(d,0,sizeof(d));}
void set(){
for(int i=0;i<=4;i++)
for(int j=0;j<=4;j++)
if(i==j) d[i][j]=1;
else d[i][j]=0;
}
};
Matrix operator * (Matrix a,Matrix b){
int i,j,k;
Matrix c;
for(i=0;i<=4;i++)
for(j=0;j<=4;j++)
for(k=0;k<=4;k++)
c.d[i][j] = (c.d[i][j] + (LL)a.d[i][k]*b.d[k][j])%MOD;
return c;
}
Matrix pow(Matrix x,LL k){
Matrix re;re.set();
for(;k;k/=2,x = x*x)
if(k&1)re = re*x;
return re;
}
LL n;
LL scan(){LL i=0;cin >> i;return i;}
int main(){
int i,j;
LL A0,AX,AY,B0,BX,BY;
//freopen("in.txt","r",stdin);
short ok = 1;
while(cin >> n){
A0 = scan();
AX = scan();
AY = scan();
B0 = scan();
BX = scan();
BY = scan();
if(n==0){printf("0\n");continue;}
Matrix fir,next;
fir.d[0][0] = 1;
fir.d[0][1] = A0;
fir.d[0][2] = B0;
fir.d[0][3] = A0*B0%MOD;
fir.d[0][4] = 0;

//0
next.d[0][0] = 1;
//1
next.d[0][1] = AY;
next.d[1][1] = AX;
//2
next.d[0][2] = BY;
next.d[2][2] = BX;
//3
next.d[3][3] = AX*BX%MOD;
next.d[1][3] = AX*BY%MOD;
next.d[2][3] = AY*BX%MOD;
next.d[0][3] = AY*BY%MOD;
//4-ans
next.d[3][4] = 1;
next.d[4][4] = 1;
fir = fir * pow(next,n-1);

fir.d[0][4] = (fir.d[0][4]+fir.d[0][3])%MOD;
printf("%I64d\n",fir.d[0][4]);
}
return 0;
}

第一眼感觉是等比数列随便推式子
然后推了一页纸发现过不了样例……
忘记了等比数列前缀和需要讨论公比是否等于1的情况……
也就是说我还要推三个式子
疯了……
这时zky神犇说:能不能矩阵乘法啊
于是矩阵乘法水掉了……
但是由于吃屎的有道翻译
它把 nonnegative 翻译成了“正”!!!!!导致我WA了一上午我去年买了个表!!!
题解:
矩形乘法构造矩阵
需要五个数:1,ai,bi,ai*bi,sigma(ai-1 * bi-1)
其中1的位置是用来处理常数项的,具体构造转移矩阵的方法看代码吧不说了
  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017