bzoj1875 边点互换+矩乘

时间:2022-09-02 17:27:13

https://www.lydsy.com/JudgeOnline/problem.php?id=1875

题意 HH有个一成不变的习惯,喜欢饭后百步走。所谓百步走,就是散步,就是在一定的时间 内,走过一定的距离。 但

是同时HH又是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人,所以他每
天走过的路径都不完全一样,他想知道他究竟有多 少种散步的方法。 现在给你学校的地图(假设每条路的长度都
是一样的都是1),问长度为t,从给定地 点A走到给定地点B共有多少条符合条件的路径
 
开始没有看到不能走回头路的条件,以为是道人尽皆知傻逼矩阵快速幂,WA了好几发后才发现这个奇形怪状的条件。
既然不能走回头路,我们就不能用点构造矩阵了,考虑直接用边来构造矩阵,表示边与边之间到达的关系。
dp[i][j]表示边i通过k次操作到达边j的数目。
我们建立两个虚点,一个x指向所有起点为S的边,一个y被所有终点为T的边指向,最终x需要经过K + 1条边到达y的数目即为答案
构造矩阵即可。
#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 边点互换+矩乘的更多相关文章

  1. BZOJ1875&colon; &lbrack;SDOI2009&rsqb;HH去散步 图上边矩乘

    这道题十分的坑…… 我作为一只连矩乘都不太会的渣渣看到这道题就只能神搜了….. 首先说一下普通的矩乘求方案,就是高出邻接矩阵然后一顿快速幂….. 矩乘一般就是一些秘制递推….. 再说一下这道题,我们可 ...

  2. bzoj3157国王奇遇记&lpar;秦九韶算法&plus;矩乘&rpar;&amp&semi;&amp&semi;bzoj233AC达成

    bz第233题,用一种233333333的做法过掉了(为啥我YY出一个算法来就是全网最慢的啊...) 题意:求sigma{(i^m)*(m^i),1<=i<=n},n<=10^9,m ...

  3. 大小写互换-&quot&semi;数字字符串&quot&semi;转换成数字

    今天穿着hacker浑浊马甲在百度编程课堂实训习题中发现了这个很简单的问题,就做了下. 为了考虑输入的是否是数字,结果写好后竟然超时了. 不过里面用到的将字符串装换成数字的方法,感觉是个收获,因此在此 ...

  4. ytu 1050&colon;写一个函数,使给定的一个二维数组(3&&num;215&semi;3)转置,即行列互换(水题)

    1050: 写一个函数,使给定的一个二维数组(3×3)转置,即行列互换 Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 154  Solved: 112[ ...

  5. for循环中i--的妙用 及 两变量互换数值的问题

    int[] array = new int[4]; for(int i = 0; i < array.length; i++){ array[i] = (int)(Math.random() * ...

  6. 球形环境映射之angular与latlong格式互换

    这么做只是纯好奇,因为这种格式互换在实际中是没有意义的,下面映射方式互换的贴图说明了一切. 刚开始打算使用matlab进行贴图映射方式的转换,但许久不用很是生疏,而且生成图片要考虑很多事情,尤其是生成 ...

  7. css相对定位&plus;浮动实现元素位置互换

    1.设置元素透明度 opacity:0.5; // w3c filter:alpha(opacity=50); //IE 2 position:relative; float:left; 一起使用的效 ...

  8. Java经典实例:纪元秒和本地日期时间互换

    Java版本:1.8开始 import java.time.Instant; import java.time.ZoneId; import java.time.ZonedDateTime; /** ...

  9. AC日记——大小写字母互换 openjudge 1&period;7 14

    14:大小写字母互换 总时间限制:  1000ms 内存限制:  65536kB 描述 把一个字符串中所有出现的大写字母都替换成小写字母,同时把小写字母替换成大写字母. 输入 输入一行:待互换的字符串 ...

随机推荐

  1. CPUID指令简单调用

    关于CPUID指令,可以看*的相关介绍 https://en.wikipedia.org/wiki/CPUID 在windows下可以调用__cpuid和__cpuidex这两个函数,__cpu ...

  2. sharepoint 2013 持续爬网

    能否对所有类型的内容源都使用连续爬网?不能.连续爬网仅适用于 SharePoint 型内容源.所有其他类型的内容源将继续选择增量爬网和完全爬网. 使用连续爬网是否会给存储库增加额外负载?连续爬网的资源 ...

  3. &lbrack;原创&rsqb;Devexpress XtraReports 系列 9 创建邮件合并报表

    昨天发表了Devexpress XtraReports系列第八篇[原创]Devexpress XtraReports 系列 8 创建Drill-Through报表,今天我们继续. 今天的主题是创建邮件 ...

  4. ASP&period;NET Web Service如何工作(2)

    ASP.NET Web Service如何工作(2) [日期:2003-06-26] 来源:CSDN  作者:sunnyzhao(翻译) [字体:大 中 小] HTTP管道一旦调用了.asmx句柄,便 ...

  5. NET实现的DDD、CQRS与微服务架构

    WeText项目:一个基于.NET实现的DDD.CQRS与微服务架构的演示案例 最近出于工作需要,了解了一下微服务架构(Microservice Architecture,MSA).我经过两周业余时间 ...

  6. iOS面试必看经典试题分析

    > **不用临时变量怎么实现两个数据的交换?** 方式一:加减法的运算方式求解new_b = a - b + b = a;new_a = a + b - a = b;一个简单的运算方式,最重要的 ...

  7. ABP官方文档翻译 8&period;2 SignalR集成

    SignalR集成 介绍 安装 服务器端 客户端 建立连接 內建特征 通知 在线客户端 PascalCase与CamelCase对比 你的SignalR代码 介绍 ABP中的Abp.Web.Signa ...

  8. python 三大框架之一Django入门

    Django 是从真实世界的应用中成长起来的,它是由 堪萨斯(Kansas)州 Lawrence 城中的一个 网络开发小组编写的. 它诞生于 2003 年秋天,那时 Lawrence Journal- ...

  9. python学习------面向对象的程序设计

    一 面向对象的程序设计的由来 1940年以前:面向机器 最早的程序设计都是采用机器语言来编写的,直接使用二进制码来表示机器能够识别和执行的指令和数 据.简单来说,就是直接编写 和 的序列来代表程序语言 ...

  10. 安装git-review

    参考 https://blog.csdn.net/qq18340811755/article/details/80965188 当yum install git-review安装失效,没有安装包时,只 ...