「Bzoj1875」「Luogu2151」HH去散步

来源和评测点

SDOI2009 Day1
Bzoj1875
Luogu2151

题目

「题目大意」
HH有个一成不变的习惯,喜欢饭后百步走。
所谓百步走,就是散步,就是在一定的时间内,走过一定的距离。
但是同时HH又是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人,所以他每天走过的路径都不完全一样,
他想知道他究竟有多少种散步的方法。
现在给你学校的地图(假设每条路的长度都是一样的都是1),问长度为t,
从给定地点A走到给定地点B共有多少条符合条件的路径
「输入格式」
第一行:五个整数N,M,t,A,B。
N表示学校里的路口的个数
M表示学校里的 路的条数
t表示HH想要散步的距离
A表示散步的出发点
B则表示散步的终点。
接下来M行
每行一组Ai,Bi,表示从路口Ai到路口Bi有一条路。
数据保证Ai != Bi,但不保证任意两个路口之间至多只有一条路相连接。
路口编号从0到N -1。
同一行内所有数据均由一个空格隔开,行首行尾没有多余空格。没有多余空行。
答案模45989。
「限定条件」
N≤20,M≤60,t≤2^30,0≤A,B
「输出格式」
一行,表示答案。
「输入样例」
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2
「输出样例」
4
「样例解释」

刷题记录

30min
3WA
1AC

分析

不能立刻走回头路!
没理解这句话还以为是煞笔题……

首先,考虑dp方程,
用边去推导(主要是因为不能立刻走回头路,而且有重边,这都主要跟边有关系)
$f[i][k]=\sum f[j][k2] (k:j=>i,k!=oth[k2])$
那么因为t灰常大,但是这个「上一条边」是与以后决策无关的
所以引入矩阵乘法,利用快速幂加速

设起始边i,终止边j
构造t=1的初始矩阵A
当$y[i]=x[j]$,i连接j,且$i!=oth[j]$
则$A[j][i]=1$

为什么是反的?
考虑矩阵乘法的定义,以及我们通常用的列向量:
$A[][]\times st[i][1]=ed[j][1]$
发现必须是$A[j][i]$

这个判断矩乘的方法是我自己想的,好像网上也没人这样用。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
//*******************全局常量*******************
const int MAXN=150;
const int MOD=45989;
//*******************全局定义*******************
struct Martix
{
int row,col;
int m[MAXN][MAXN];
Martix(int r=0,int c=0)
{
row=r;col=c;
memset(m,0,sizeof(m));
}
};
//*******************实现*******************
Martix one(int row)
{
Martix ans(row,row);
for(int i=1;i<=row;i++) ans.m[i][i]=1;
return ans;
}
Martix mul(Martix a,Martix b)
{
Martix c(a.row,b.col);
for(int i=1;i<=c.row;i++)
for(int j=1;j<=c.col;j++)
for(int k=1;k<=a.col;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%MOD)%MOD;
return c;
}
Martix power(Martix a,int e)
{
Martix ans=one(a.row);
while(e>0)
{
if(e&1) ans=mul(ans,a);
a=mul(a,a);e>>=1;
}
return ans;
}

struct Edge
{
int x,y,oth;
}e[MAXN];
int ln=0;
void ins(int x,int y)
{
e[++ln]=(Edge){x,y,ln+1};
e[++ln]=(Edge){y,x,ln-1};
}
//*******************主函数*******************
int main()
{
int n,m,t,st,ed;scanf("%d%d%d%d%d",&n,&m,&t,&st,&ed);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y);
}
Martix stm(ln,1);for(int k=1;k<=ln;k++) stm.m[k][1]=(e[k].x==st);

Martix A(ln,ln);
for(int k1=1;k1<=ln;k1++)
for(int k2=1;k2<=ln;k2++)
A.m[k2][k1]=(e[k1].oth!=k2 and e[k1].y==e[k2].x);

Martix edm=mul(power(A,t-1),stm);

int ans=0;
for(int k=1;k<=ln;k++) if(e[k].y==ed) ans=(ans+edm.m[k][1])%MOD;
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/3469.html
转载请注明出处,谢谢!