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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1875][SDOI2009]HH去散步  

2014-12-14 19:42:41|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1875: [SDOI2009]HH去散步

卧槽会考完了智商下降了
妈蛋我快速幂都写不对了……
还企图用
a=a*a;a=a*a;
达成a = a^3这种效果。。
啊顺便说一声,BZOJ的题面格式挂了,T≤2^30
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int MOD = 45989;
const int N = 20+10;
const int M = 60*2+10;
int n,m,start,end,T;
struct Matrix{
int n,m;
int d[M][M];
}ans,zht;
Matrix operator * (const Matrix &a,const Matrix &b){
Matrix c;int i,j,k;
c.n = a.n;c.m = b.m;
for(i=1;i<=c.n;i++)
for(j=1;j<=c.m;j++)
c.d[i][j] = 0;
for(i=1;i<=c.n;i++)
for(j=1;j<=c.m;j++)
for(k=1;k<=a.m;k++)
c.d[i][j] = (c.d[i][j]+a.d[i][k]*b.d[k][j])%MOD;
return c;
}
Matrix pow(Matrix x,int k){
k--;Matrix re = x;
if(k<0)printf("RE");
for(;k;k/=2,x=x*x)
if(k&1)re = re*x;
return re;
}
struct Edge{
int a,b;
Edge(){}
Edge(int aa, int bb):a(aa),b(bb){}
}edges[M];
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b,t;
n = scan();m = scan();t = scan();
start = scan()+1;end = scan()+1;
if(start == end && t==0){printf("1\n");return 0;}
if(start != end && t==0){printf("0\n");return 0;}
memset(zht.d,0,sizeof(zht.d));
for(i=1;i<=m;i++){
a = 1+scan();b = 1+scan();
if(a>b)swap(a,b);
edges[T++] = Edge(a,b);
edges[T++] = Edge(b,a);
}
for(i=0;i<T;i++)
for(j=0;j<T;j++)
if(edges[i].b == edges[j].a && i!=(j^1)) zht.d[j+1][i+1] = 1;
for(i=0;i<T;i++){
if(edges[i].a == start) zht.d[i+1][T+1] = 1;
if(edges[i].b == end) zht.d[T+2][i+1] = 1;
}
memset(ans.d,0,sizeof(ans.d));
ans.m = 1;
zht.n = zht.m = ans.n = T+2;

ans.d[T+1][1] = 1;
zht = pow(zht,t+1);
ans = zht*ans;
printf("%d\n",ans.d[T+2][1]);
return 0;
}

题解:
矩阵乘法加速DP。
建立一个起点和一个终点,然后把每条边拆成两个方向的两条,这样就保证不会走回头路。
建矩阵随便一搞就行啦
(我一开始看完了一想……怎么这么水直接暴力DP不就好了,上网一搜题解全是矩阵乘法,然后发现是题目格式挂了233)
  评论这张
 
阅读(301)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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