题解 P2151 【[SDOI2009]HH去散步】
发一个用边进行动态规划的方法吧
我们先列出动态规划的递推方程:
设f[t][i]表示已经走到距离t,并且第t步经过边i的方案总数,则f[t][i]=Σf[t-1][j],其中边j可以直接连向边i
很显然一条无向边应该拆分为两条有向边,因为行走在同一条边的不同方向上,更新方案数的方法是不同的
最后,根据动态规划方程的特点和t比较大的事实,我们考虑使用矩阵优化
最后贴代码:
#include<bits/stdc++.h>
using namespace std;
#define MAXN 2*60+10
#define MOD 45989
int n, m, t, a, b, l[MAXN], r[MAXN];
int matrix[3][MAXN][MAXN], st[MAXN], en[MAXN], ans=0;
void Input(){
memset(matrix, 0, sizeof(matrix));
memset(st, 0, sizeof(st));
memset(en, 0, sizeof(en));
scanf("%d%d%d%d%d", &n, &m, &t, &a, &b);
for(int i=0; i<m; i++){
scanf("%d%d", &l[i*2], &r[i*2]);
//建立反向边
//为了后面方便判断一条边是否为另一条边的反向边,一对反向边的编号是相邻的
l[i*2+1]=r[i*2], r[i*2+1]=l[i*2];
}
}
void Mul(int target, int base){//矩阵乘法
memset(matrix[2], 0, sizeof(matrix[2]));
for(int i=0; i<2*m; i++)
for(int j=0; j<2*m; j++)
for(int k=0; k<2*m; k++)
matrix[2][i][j]=(matrix[2][i][j]+(matrix[target][i][k]*matrix[base][k][j])%MOD)%MOD;
for(int i=0; i<2*m; i++)
for(int j=0; j<2*m; j++)
matrix[target][i][j]=matrix[2][i][j];
}
void Work(){
//构造起始向量
for(int i=0; i<2*m; i++)
l[i]==a?st[i]=1:0;
//构造单位矩阵
for(int i=0; i<2*m; i++)
matrix[1][i][i]=1;
//构造矩阵
//两条边相连当且仅当它们首尾相连且不是反向边
//注意了:不能认为连接一对相同点的边是反向边,因为题目没有说两点之间仅有一条边
for(int i=0; i<2*m; i++)
for(int j=0; j<2*m; j++)
if(l[i]==r[j] && i!=(j^1))
matrix[0][i][j]=1;
t--;//注意t--,因为起始向量表示的是已经走了1步的情况,所以再走t-1步就可以了
while(t){//矩阵快速幂
if(t&1) Mul(1, 0);
Mul(0, 0), t>>=1;
}
//构造终止向量
for(int i=0; i<2*m; i++)
for(int j=0; j<2*m; j++)
en[i]=(en[i]+matrix[1][i][j]*st[j])%MOD;
//统计答案
for(int i=0; i<2*m; i++)
r[i]==b?ans=(ans+en[i])%MOD:0;
printf("%d\n", ans);
}
int main(){
freopen("walk.in","r", stdin);
freopen("walk.out","w", stdout);
Input();
Work();
fclose(stdin); fclose(stdout);
return 0;
}