【luogu P2151】HH去散步(DP)(矩阵乘法)
HH去散步
题目链接:luogu P2151
题目大意
给你一个无向图,然后给你起点终点走的路径数量,然后每次走不能走那条边的回头路,然后问你有多少走的方案。
思路
首先胡一下正常的做法吧。(乐)
就如果可以回头路那就简单,但是不能回头,考虑把它区分开来。
亦或者说你可以视作把边看做有向,然后再看做点,那双向边之间不能连边,就可以正常跑矩阵乘法啦。
这里给的是一种跟
m
m
m 无关的做法。
设
f
x
,
y
,
z
f_{x,y,z}
fx,y,z 为最后到的两个点是
x
,
y
x,y
x,y,走了
z
z
z 步的方案。(这样你就可以防止走回头路)
f
x
,
y
,
z
=
g
x
,
y
∑
i
=
1
n
f
i
,
x
,
z
−
1
−
f
y
,
x
,
z
−
1
f_{x,y,z}=g_{x,y}\sum\limits_{i=1}^nf_{i,x,z-1}-f_{y,x,z-1}
fx,y,z=gx,yi=1∑nfi,x,z−1−fy,x,z−1
但是矩阵边长为
n
2
n^2
n2 不行(亦或者说不够好,在某个地方不太行)
考虑你答案要求什么(
∑
i
=
1
n
f
i
,
T
,
L
\sum\limits_{i=1}^nf_{i,T,L}
i=1∑nfi,T,L)
g
1
x
,
z
=
∑
i
=
1
n
f
x
,
i
,
z
=
∑
i
=
1
n
(
g
x
,
i
∑
j
=
1
n
f
j
,
x
,
z
−
1
−
f
i
,
x
,
z
−
1
)
=
∑
i
=
1
n
g
x
,
i
g
2
x
,
z
−
1
−
g
2
x
,
z
−
1
=
g
2
x
,
z
−
1
(
∑
i
=
1
n
g
x
,
i
−
1
)
g1_{x,z}=\sum\limits_{i=1}^nf_{x,i,z}=\sum\limits_{i=1}^n(g_{x,i}\sum\limits_{j=1}^nf_{j,x,z-1}-f_{i,x,z-1})=\sum\limits_{i=1}^ng_{x,i}g2_{x,z-1}-g2_{x,z-1}=g2_{x,z-1}(\sum\limits_{i=1}^ng_{x,i}-1)
g1x,z=i=1∑nfx,i,z=i=1∑n(gx,ij=1∑nfj,x,z−1−fi,x,z−1)=i=1∑ngx,ig2x,z−1−g2x,z−1=g2x,z−1(i=1∑ngx,i−1)
g
2
y
,
z
=
∑
i
=
1
n
f
i
,
y
,
z
=
∑
i
=
1
n
(
g
i
,
y
∑
j
=
1
n
f
j
,
i
,
z
−
1
−
f
y
,
i
,
z
−
1
)
=
∑
i
=
1
n
g
x
,
i
g
2
i
,
z
−
1
−
g
1
y
,
z
−
1
g2_{y,z}=\sum\limits_{i=1}^nf_{i,y,z}=\sum\limits_{i=1}^n(g_{i,y}\sum\limits_{j=1}^nf_{j,i,z-1}-f_{y,i,z-1})=\sum\limits_{i=1}^ng_{x,i}g2_{i,z-1}-g1_{y,z-1}
g2y,z=i=1∑nfi,y,z=i=1∑n(gi,yj=1∑nfj,i,z−1−fy,i,z−1)=i=1∑ngx,ig2i,z−1−g1y,z−1
然后弄出这两个东西,你发现你可以只保留这两个的信息做矩阵乘法,然后矩阵边长就变成 2 n 2n 2n 就可以过啦!
然后如果多组询问不同 L , T L,T L,T,那就把快速幂改成倍增,也是一样的道理。
代码
#include<cstdio>
#include<cstring>
#define ll long long
//#define mo 998244353
#define mo 45989
using namespace std;
const int N = 105;
int n, m, Q, S, T, g[N][N];
int st[N << 1], jump[60][N << 1][N << 1], ans[N << 1], tmp[N << 1];
ll L;
int add(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int mul(int x, int y) {return 1ll * x * y % mo;}
void Init() {
for (int i = 1; i <= n; i++) st[S] = add(st[S], g[S][i]);
for (int i = 1; i <= n; i++) st[n + i] = add(st[n + i], g[S][i]);
for (int i = 1; i <= n; i++) {//g1
int tmp = mo - 1; for (int j = 1; j <= n; j++) tmp = add(tmp, g[i][j]);
jump[0][n + i][i] = tmp;
}
for (int i = 1; i <= n; i++) {//g2
for (int j = 1; j <= n; j++) jump[0][n + j][n + i] = add(jump[0][n + j][n + i], g[i][j]);
jump[0][i][n + i] = add(jump[0][i][n + i], mo - 1);
}
for (int z = 1; z < 60; z++) {
for (int k = 1; k <= (n << 1); k++)
for (int i = 1; i <= (n << 1); i++)
for (int j = 1; j <= (n << 1); j++)
jump[z][i][j] = add(jump[z][i][j], mul(jump[z - 1][i][k], jump[z - 1][k][j]));
}
}
int main() {
// freopen("ancient.in", "r", stdin);
// freopen("ancient.out", "w", stdout);
// scanf("%d %d %d %d", &n, &m, &Q, &S);
scanf("%d %d %d %d %d", &n, &m, &L, &S, &T); S++; T++;
for (int i = 1; i <= m; i++) {
int x, y; scanf("%d %d", &x, &y);
x++; y++;
g[x][y]++; g[y][x]++;
}
Init();
// while (Q--) {
// scanf("%d %lld", &T, &L);
// if (!L) {printf("%d\n", (S == T) ? 1 : 0); continue;}
if (!L) {printf("%d\n", (S == T) ? 1 : 0); return 0;}
L--; memcpy(ans, st, sizeof(ans));
for (int z = 59; z >= 0; z--) if ((L >> z) & 1) {
for (int k = 1; k <= (n << 1); k++)
for (int j = 1; j <= (n << 1); j++)
tmp[j] = add(tmp[j], mul(ans[k], jump[z][k][j]));
memcpy(ans, tmp, sizeof(ans)); memset(tmp, 0, sizeof(tmp));
}
printf("%d\n", ans[n + T]);
// }
return 0;
}
相关文章
- 深度学习-神经网络:卷积的实现方法【直接法(精度没损失)、GEMM(矩阵乘法,精度没损失)、FFT(傅里叶变换,精度有损失)、Winograd(精度有损失)】
- 【BZOJ】1009: [HNOI2008]GT考试(dp+矩阵乘法+kmp+神题)
- 【机器学习】【条件随机场CRF-3】条件随机场的参数化形式详解 + 画出对应的状态路径图 + 给出对应的矩阵表示
- 各种图的创建以及广度,深度优先遍历(临接矩阵存储)
- 在Pytorch上使用稀疏矩阵
- 概率与影响矩阵
- Python之Numpy:线性代数/矩阵运算
- POJ 3070 Fibonacci (矩阵)
- 【概念记录】什么是 行最简形 矩阵?
- 外参矩阵转四元数,左右手坐标系转化1
- 力扣: 240搜索二维矩阵
- (8)向量范数与矩阵范数
- Duanxx的Design abroad: C++矩阵运算库Eigen 概要
- 27复矩阵和快速傅里叶变换
- 两个矩阵中的dp题的差异
- czy的后宫——矩阵快速幂优化DP
- 【luogu CF645E】Intellectual Inquiry(DP)(结论)(矩阵乘法)
- 【ybtoj高效进阶 21278】内需消费(线段树)(广义矩阵乘法)(DP)
- 【ybt金牌导航3-1-4】【luogu P1129】矩阵游戏
- [LeetCode] 240. Search a 2D Matrix II 搜索一个二维矩阵 II