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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1898][Zjoi2004]Swamp 沼泽鳄鱼  

2015-03-11 15:34:49|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1898: [Zjoi2004]Swamp 沼泽鳄鱼

在Debian下写代码有点蛋疼

题解在代码下方

//我能吞下玻璃而不伤身体!
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 50+10;
const int MOD = 10000;
int n,m,k,s,t,nf,tmp[5];
struct Matrix{
int n,m,d[N][N];
void set(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j] = (i==j);
}
void clear(){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j] = 0;
}
void eat(int x){
for(int i=1;i<=m;i++)d[x][i]=0;
}
}ans,zht[13];
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] += a.d[i][k]*b.d[k][j];
if(c.d[i][j] >= MOD)c.d[i][j]%=MOD;
}return c;
}
Matrix kpow(Matrix x,int k){
Matrix re;re.set();
for(;k;k/=2,x=x*x)
if(k&1)re=re*x;
return re;
}
void print(const Matrix&a){
int i,j;
for(i=1;i<=a.n;i++)
{
for(j=1;j<=a.m;j++)printf("%d ",a.d[i][j]);
printf("\n");
}
}
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
int main(){
int i,j,a,b;
n = scan();m = scan();
s = scan();t = scan();
k = scan();s++;t++;
ans.n=n; ans.m=1;
ans.clear();
ans.d[s][1]=1;
for(i=1;i<=12;i++){
zht[i].n=zht[i].m=n;
zht[i].clear();
}
for(i=1;i<=m;i++){
a = scan();b = scan();
a++;b++;
for(j=1;j<=12;j++){
zht[j].d[a][b]++;
zht[j].d[b][a]++;
}
}
//print(zht[1]);
nf = scan();
for(i=1;i<=nf;i++){
a = scan();
for(j=0;j<a;j++){
tmp[j]=scan()+1;
}
for(j=1;j<=12;j++){
zht[j].eat(tmp[(j)%a]);
}
}
//print(zht[2]);

for(i=2;i<=12;i++){
zht[i]=zht[i]*zht[i-1];
}

//ans = zht[1]*ans;
//print(ans);

//print(zht[1]);
zht[0]=kpow(zht[12],k/12);
if(k%12)zht[0]=zht[k%12]*zht[0];
ans = zht[0]*ans;
//print(ans);
printf("%d\n",ans.d[t][1]);
return 0;
}

题解:
    矩阵乘法(其实BZOJ下面已经剧透了……而且我老早就听说这是一道经典题
    没有鱼的话大家都会……
    但是现在有一堆蛋疼的鱼,导致每次转移不太一样
    然后发现鱼的周期的lcm=12很小,所以转移是每12次为一周期的
    所以矩阵转移一下整的周期,不完整的周期暴力转移一下就好了
  评论这张
 
阅读(346)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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