[LuoguP2151][SDOI2009]HH去散步_递推_矩阵乘法_图论

时间:2024-09-14 11:34:56

HH去散步

题目链接https://www.luogu.org/problem/P2151

数据范围:略。


题解

数据范围好小,让人不禁想用一些毒瘤算法,但是失败了。

这种类似时间啊这种有点重复味道的变量特别特别大,连枚举都会$T$的时候,而且存在一些数据比较小,我们考虑矩阵乘法。

至于状态,开始的时候想到的一定是$dp_{(i,j)}$表示时刻$i$到达了点$j$的方案数。

但是我们没办法判断下一条边和上次到达$j$的边是不是一条。

于是想办法怎么能把最后一条边压进状态。

显然,我们可以把无向边拆成有向边,然后将$j$替换成边的编号即可。

转移傻逼,可以矩乘。