HH
又是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为HH
是个喜欢变化的人,所以他每天走过的路径都不完全一样,他想知道他究竟有多少种散步的方法。
现在给你学校的地图(假设每条路的长度都是一样的都是$1$),问长度为$t$,从给定地点$A$走到给定地点$B$共有多少条符合上述条件的路径。
链接
题解
可以发现这是一道dp。
如果令状态为$dp[i][t]$,在第$i$个点,再走t步到达B点的方案数。但是我们注意到这个就很难满足:
他不会立刻沿着刚刚走来的路走回
的限制条件。
所以我们为了体现出刚走过的边,同时还能体现出刚走过的点,就重新设计一下状态:
令$dp[e][t]$为刚刚走过第$e$条边,再走$t$步到达$B$点的方案数。
具体实现的时候要建两条单向边,然后状态转移方程大概是:
$$
dp[e][t] = \sum dp[e’][t-1]
$$
其中$e’$为所有从$e.to$出发的边,除了$e$的反向边。
注意到这里$t$的范围比较大,对于任意时候的$t$和某个$e$,转移的路径,也就是$e’$都不会变,所以我们用矩阵快速幂优化这一过程。
这里的模数要用define
样式的比较好,对于常数比较有利。
时间复杂度:$O((2m)^3 \times \log{t})$
代码
1 |
|