https://www.lydsy.com/JudgeOnline/problem.php?id=1875
题意 HH有个一成不变的习惯,喜欢饭后百步走。所谓百步走,就是散步,就是在一定的时间 内,走过一定的距离。 但
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = ;
const int INF = 0x3f3f3f3f;
const int mod = ;
int N,M,tmp,K,tot;
int S,T;
struct Mat{
LL a[maxn][maxn];
void init(){
Mem(a,);
}
}base;
struct Edge{
int u,v;
Edge(int u = ,int v = ):u(u),v(v) {}
}edge[maxn];
Mat operator * (Mat a,Mat b){
Mat ans; ans.init();
for(int i = ; i <= tot ; i ++){
for(int j = ; j <= tot; j ++){
for(int k = ; k <= tot; k ++){
ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
}
}
}
return ans;
}
Mat operator ^ (Mat a,int b){
Mat x,y = a;
x.init();
For(i,,tot) x.a[i][i] = ;
while(b){
if(b & ) x = x * y;
b >>= ;
y = y * y;
}
return x;
}
void solve(){
base = base ^ (K + );
printf("%lld",base.a[][]);
}
int main()
{
scanf("%d%d%d%d%d",&N,&M,&K,&S,&T);
base.init(); tot = ;
For(i,,M){
int u,v; Sca2(u,v);
edge[tot++] = Edge(u,v);
edge[tot++] = Edge(v,u);
}
tot--;
For(i,,tot){
if(edge[i].u == S) base.a[][i] = ;
if(edge[i].v == T) base.a[i][] = ;
For(j,,tot){
if(edge[i].v == edge[j].u && (i ^ j ) != ) base.a[i][j] = ;
}
}
solve();
#ifdef VSCode
system("pause");
#endif
return ;
}
bzoj1875 边点互换+矩乘的更多相关文章
-
BZOJ1875: [SDOI2009]HH去散步 图上边矩乘
这道题十分的坑…… 我作为一只连矩乘都不太会的渣渣看到这道题就只能神搜了….. 首先说一下普通的矩乘求方案,就是高出邻接矩阵然后一顿快速幂….. 矩乘一般就是一些秘制递推….. 再说一下这道题,我们可 ...
-
bzoj3157国王奇遇记(秦九韶算法+矩乘)&;&;bzoj233AC达成
bz第233题,用一种233333333的做法过掉了(为啥我YY出一个算法来就是全网最慢的啊...) 题意:求sigma{(i^m)*(m^i),1<=i<=n},n<=10^9,m ...
-
大小写互换-";数字字符串";转换成数字
今天穿着hacker浑浊马甲在百度编程课堂实训习题中发现了这个很简单的问题,就做了下. 为了考虑输入的是否是数字,结果写好后竟然超时了. 不过里面用到的将字符串装换成数字的方法,感觉是个收获,因此在此 ...
-
ytu 1050:写一个函数,使给定的一个二维数组(3&#215;3)转置,即行列互换(水题)
1050: 写一个函数,使给定的一个二维数组(3×3)转置,即行列互换 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 154 Solved: 112[ ...
-
for循环中i--的妙用 及 两变量互换数值的问题
int[] array = new int[4]; for(int i = 0; i < array.length; i++){ array[i] = (int)(Math.random() * ...
-
球形环境映射之angular与latlong格式互换
这么做只是纯好奇,因为这种格式互换在实际中是没有意义的,下面映射方式互换的贴图说明了一切. 刚开始打算使用matlab进行贴图映射方式的转换,但许久不用很是生疏,而且生成图片要考虑很多事情,尤其是生成 ...
-
css相对定位+浮动实现元素位置互换
1.设置元素透明度 opacity:0.5; // w3c filter:alpha(opacity=50); //IE 2 position:relative; float:left; 一起使用的效 ...
-
Java经典实例:纪元秒和本地日期时间互换
Java版本:1.8开始 import java.time.Instant; import java.time.ZoneId; import java.time.ZonedDateTime; /** ...
-
AC日记——大小写字母互换 openjudge 1.7 14
14:大小写字母互换 总时间限制: 1000ms 内存限制: 65536kB 描述 把一个字符串中所有出现的大写字母都替换成小写字母,同时把小写字母替换成大写字母. 输入 输入一行:待互换的字符串 ...
随机推荐
-
CPUID指令简单调用
关于CPUID指令,可以看*的相关介绍 https://en.wikipedia.org/wiki/CPUID 在windows下可以调用__cpuid和__cpuidex这两个函数,__cpu ...
-
sharepoint 2013 持续爬网
能否对所有类型的内容源都使用连续爬网?不能.连续爬网仅适用于 SharePoint 型内容源.所有其他类型的内容源将继续选择增量爬网和完全爬网. 使用连续爬网是否会给存储库增加额外负载?连续爬网的资源 ...
-
[原创]Devexpress XtraReports 系列 9 创建邮件合并报表
昨天发表了Devexpress XtraReports系列第八篇[原创]Devexpress XtraReports 系列 8 创建Drill-Through报表,今天我们继续. 今天的主题是创建邮件 ...
-
ASP.NET Web Service如何工作(2)
ASP.NET Web Service如何工作(2) [日期:2003-06-26] 来源:CSDN 作者:sunnyzhao(翻译) [字体:大 中 小] HTTP管道一旦调用了.asmx句柄,便 ...
-
NET实现的DDD、CQRS与微服务架构
WeText项目:一个基于.NET实现的DDD.CQRS与微服务架构的演示案例 最近出于工作需要,了解了一下微服务架构(Microservice Architecture,MSA).我经过两周业余时间 ...
-
iOS面试必看经典试题分析
> **不用临时变量怎么实现两个数据的交换?** 方式一:加减法的运算方式求解new_b = a - b + b = a;new_a = a + b - a = b;一个简单的运算方式,最重要的 ...
-
ABP官方文档翻译 8.2 SignalR集成
SignalR集成 介绍 安装 服务器端 客户端 建立连接 內建特征 通知 在线客户端 PascalCase与CamelCase对比 你的SignalR代码 介绍 ABP中的Abp.Web.Signa ...
-
python 三大框架之一Django入门
Django 是从真实世界的应用中成长起来的,它是由 堪萨斯(Kansas)州 Lawrence 城中的一个 网络开发小组编写的. 它诞生于 2003 年秋天,那时 Lawrence Journal- ...
-
python学习------面向对象的程序设计
一 面向对象的程序设计的由来 1940年以前:面向机器 最早的程序设计都是采用机器语言来编写的,直接使用二进制码来表示机器能够识别和执行的指令和数 据.简单来说,就是直接编写 和 的序列来代表程序语言 ...
-
安装git-review
参考 https://blog.csdn.net/qq18340811755/article/details/80965188 当yum install git-review安装失效,没有安装包时,只 ...