BZOJ 1898 沼泽鳄鱼(矩阵快速幂)
2024-10-21 15:41:08
没有食人鱼不是裸题吗,用一个向量表示从s到1..N的距离,然后不停乘邻接矩阵行了,当然快速幂
有食人鱼,发现食人鱼最多十二个邻接矩阵一循环,处理出12个作为1个然后快速幂行了
怎么处理呢?
假设食人鱼在j时刻到达x这个点,那么j时刻的邻接矩阵x这一列全是0,因为他要求下一个矩阵的贡献上不能有x这一列贡献的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=,MOD=1e4;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,s,t,k,x,y,fish,f[];
struct Mat{
int a[N][N];
Mat(){memset(a,,sizeof(a));}
void ini(){for(int i=;i<=n;i++) a[i][i]=;}
}g[],ans;
inline Mat operator *(Mat A,Mat B){
Mat C;
for(int k=;k<=n;k++)
for(int i=;i<=n;i++) if(A.a[i][k])
for(int j=;j<=n;j++) if(B.a[k][j])
C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;
return C;
}
inline Mat operator ^(Mat A,int k){
Mat ans;ans.ini();
for(;k;k>>=,A=A*A)
if(k&) ans=ans*A;
return ans;
}
void print(Mat A){
puts("hiMat");
for(int i=;i<=n;i++){
for(int j=;j<=n;j++) printf("%d ",A.a[i][j]);
puts("");
}
}
int main(){
//freopen("in.txt","r",stdin);
n=read();m=read();s=read()+;t=read()+;k=read();
for(int i=;i<=m;i++){
x=read()+;y=read()+;
for(int j=;j<=;j++) g[j].a[x][y]=g[j].a[y][x]=;
}
fish=read();
for(int i=;i<=fish;i++){
int T=read();
for(int j=;j<=T;j++) f[j]=read()+;
for(int j=;j<=;j++)
for(int k=;k<=n;k++) g[j].a[k][f[j%T+]]=;
}
g[].ini();
for(int i=;i<=;i++) g[]=g[]*g[i];
ans=g[]^(k/);
for (int i=;i<=k%;i++) ans=ans*g[i];
printf("%d",ans.a[s][t]);
}
最新文章
- RSA算法及其在iOS中的使用
- Trace-语句启动Profiler中暂停的跟踪会出现什么状况
- 如何优化sql语句
- Java垃圾收集学习笔记
- java计算组合数
- 2015年第13本(英文第9本):Murder on the Orient Express 东方快车谋杀案
- How To Tune or Test PLSQL Code Performance in Oracle D2k Forms
- JS初学之-效果没出来怎么办?-alert函数测试
- 怎样删除在Github中创建的项目
- ural1701 Ostap and Partners
- 全方位分析Objcetive-C Runtime 分类: ios技术 2015-03-11 22:29 77人阅读 评论(0) 收藏
- 四:java调接口实现发送手机短信验证码功能
- Python+PyCharm的一些基本设置:安装使用、注册码、显示行号、字体大小和快捷键等常用设置
- 圆方树简介(UOJ30:CF Round #278 Tourists)
- React面试题
- Java笔记(九)EnumMap &; EnumSet
- 项目总结17-使用layui table分页表格
- 从零开始学习MVC
- Java subList、toArray、asList 注意点
- 《深入分析JavaWeb技术内幕》学习笔记