「Bzoj 1875」「SDOI2009」HH去散步 (矩阵快速幂+图上DP)

发表于 | 分类于 | | + s

BZOJ 1875
题意：求无权无向图中$A$走$k$步到$B$的路径条数。过程中不能走过刚刚走过的边。

没有后面的条件就是模板题了
我们可以先设$dp(i,j)$为走了$i$步到$j$点，而这个没有记录上一条边，就不行了
刚开始想在状态记录前驱点，但是似乎不方便进行转移。。
那么从边的角度来考虑，设$dp(i,j)$为走了$i$步到第$j$条边终点结束，将无向边变成两条有向边。
那么转移$dp(i,j)=\sum dp(i-1,k), k,j$通过某点连接
但是这个DP还是会TLE
这个DP仔细想想可以满足矩阵乘法的要求，那么矩阵快速幂即可。

其实这里可以将边变成一些点。具体是如果一条边可以通过某个节点到另一条边，这两条边在新图中的点连一条边，这条边不能是一条无向边分化的有向边。
那么这里就构造了一个新的图矩阵，这个新图满足了上述条件，在原图中走$k$步相当于在新图中走$k-1$步，那么矩阵快速幂即可。
这个新图矩阵和前面的优化一样，所以是本质一样的算法，一个从 优化 DP 角度，一个从 Floyd 角度

知识点：
1、前向星存图 $en$ 从 $-1$ 开始
2、前向星判合法用 i>=1
3、图上边 DP
4、边转点

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MO = 45989;
    const LL MAXN = 125;

    LL n, m, t, A, B, en, hd[MAXN];

    struct edge {LL u, v, nxt;} ed[MAXN * 2];
    struct matrix {
        LL a[MAXN][MAXN];
        matrix() {ms(a, 0);}
    }whw;

    void ins(LL u, LL v) {ed[++en] = (edge){u, v, hd[u]}, hd[u] = en;}
    matrix mul(matrix a, matrix b) {
        matrix ret;
        for (LL i = 0; i <= en; ++i)
        for (LL j = 0; j <= en; ++j) 
        for (LL k = 0; k <= en; ++k) ret.a[i][j] = (ret.a[i][j] + (a.a[i][k] * b.a[k][j])) % MO;
        return ret;
    }
    matrix ksm(matrix a, LL b) {
        matrix ans, bs = a; int fl = 0;
        while (b) {
            if (b & 1) {
                if (fl) ans = mul(ans, bs); else fl = 1, ans = bs;    
            }
            bs = mul(bs, bs);
            b >>= 1;
        }
        return ans;
    }

    void clean() {
        en = -1, ms(hd, -1);
    }
    int solve() {
        scanf("%lld%lld%lld%lld%lld", &n, &m, &t, &A, &B);
        ++A, ++B;
        clean();
        for (LL u, v, i = 1; i <= m; ++i) scanf("%lld%lld", &u, &v), ins(++u, ++v), ins(v, u);

        for (LL i = 0; i <= en; ++i) 
        for (LL j = 0; j <= en; ++j) if (i != j && i != (j ^ 1) && ed[i].v == ed[j].u) whw.a[i][j] = 1;

        whw = ksm(whw, t - 1ll);

        LL ans = 0ll;
        for (LL i = hd[A]; i >= 0; i = ed[i].nxt) {
            for (LL j = hd[B]; j >= 0; j = ed[j].nxt) {
                ans = (ans + whw.a[i][j ^ 1]) % MO;
            }
        }
        printf("%lld\n", ans);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------