Different Pass a Ports(矩阵快速幂板子)
2022/8/29 6:53:01
本文主要是介绍Different Pass a Ports(矩阵快速幂板子),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Different Pass a Ports(矩阵快速幂)
题目大意:小明(化名)喜欢旅游,没到一个地方都会搜集该地的邮票并且按照旅游的顺序收藏,他可以进行K时间的旅行,每去一个地方就要花1时间。问k时间后,小明有多少种邮票的排序方式。小明从1这个点位出发。
经典的固定时间,经典的问固定时间后有多少种走法,直接矩阵快速幂(可以求出长度为固定值的路径有多少条)
AC代码
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #define ll long long using namespace std; const int mod=1e9+7; const int INF=0x3f3f3f3f; struct matrix { static const int n=110; int M[n][n]; int N; matrix(int num) { N=num; memset(M,0,sizeof(M)); } void build(){//把一个新的矩阵构造成单位阵 for(int i=1;i<=N;i++)M[i][i]=1; } int *operator[](int i){//直接取出该位置的值,就不用每次都要调用M return M[i]; } matrix operator*(matrix&a) { matrix temp(N); for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) for(int k=1;k<=N;k++) temp[i][j]=(temp[i][j]+(1LL*M[i][k]*a[k][j])%mod)%mod; return temp; } matrix operator^(long long P)//矩阵快速幂 { matrix res(N);res.build(); matrix A=*this; while(P>0){ if(P&1) res=res*A; A=A*A; P>>=1; } return res; } }; int main(void) { int N,M,K;scanf("%d %d %d",&N,&M,&K); matrix res(N); for(int i=0;i<M;i++) { int x,y;scanf("%d %d",&x,&y); res[x][y]++; res[y][x]++; } ll ans=0; res=res^K; for(int j=1;j<=N;j++) ans=(ans+res[1][j])%mod; cout<<ans<<endl; return 0; }
与这道题类似的还有这道:
可乐
这道题多了一个爆炸的选择,就相当于每个点都有向着一个爆炸这个位置移动的边,且该位置的出度为0,不能出去。只需要每个点多连一条边到爆炸这个点就行了,然后矩阵快速幂跑一遍
AC代码
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; const int maxn=110; const int INF=0x3f3f3f3f; const int mod=2017; struct matrix { static const int n=maxn; ll M[n][n]; int N; matrix(int num) { N=num; memset(M,0,sizeof(M)); } void build(){ for(int i=1;i<=N;i++)M[i][i]=1; } ll* operator[](int i){ return M[i]; } matrix operator*(matrix &a) { matrix temp(N); for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) for(int k=1;k<=N;k++) temp[i][j]=(temp[i][j]+(1LL*M[i][k]*a[k][j])%mod)%mod; return temp; } matrix operator^(ll P) { matrix res(N);res.build(); matrix A=*this; while(P>0){ if(P&1) res=res*A; A=A*A; P>>=1; } return res; } }; int main(void) { int N,M,K; scanf("%d %d",&N,&M); matrix res(N+1);res.build();//题目中有呆着原地这个选项,如果没有的话就不用 for(int i=0;i<M;i++) { int x,y; scanf("%d %d",&x,&y); res[x][y]++;//可能存在多条相同的路 res[y][x]++; } for(int i=1;i<=N;i++)res[i][N+1]++;//爆炸的情况,N+1为爆炸那个位置 scanf("%d",&K); res=res^K; ll ans=0; for(int j=1;j<=N+1;j++)ans+=res[1][j]; cout<<ans%mod<<endl; return 0; }
背模板!!背模板!!
这篇关于Different Pass a Ports(矩阵快速幂板子)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署