BZOJ1875 HH 去散步

题意

给出一张简单图,求走 $t$ 步从 $A$ 走到 $B$ 的方案数,不允许先从 $x$ 走到 $y$ 然后下一步从 $y$ 走回 $x$

题解

如果去掉”不会立刻沿着刚刚走来的路走回”这个条件,我们直接用邻接矩阵做矩阵快速幂就行了
但是加上这个条件后,发现直接用点之间的关系转移会有不合法方案被算进去

不妨将边看成点,将一条无向边拆成两条有向边,设 $f[i][j]$ 表示走 $i$ 步走到编号为 $j$ 的有向边的方案数,转移显然
将矩阵中 $a[i][j]$ 定义为边 $i$ 走到边 $j$ 的方案数,一开始显然只有可能某个点的入边对其出边有贡献,然后做 $t-1$ 次矩阵快速幂
显然 $f$ 数组的初始化为 $f[A][i]=1$ 其中 $i$ 为 $A$ 的出边,最后将 $f$ 与矩阵乘一下转移就行了
注意边的编号为 $2$ 到 $M*2+1$
复杂度 $O(M^3\log t)$

代码

#define MAX_N 27
#define MAX_M 127
#define MOD 45989

int N, M, S, T, Tid;
int idx[MAX_N][MAX_N];
int head[MAX_N], to[MAX_M], nxt[MAX_M], cap = 1;
ll t, f[MAX_M], g[MAX_M];

struct matrix {
    ll a[MAX_M][MAX_M];

    inline void init () {
        memset(a, 0, sizeof(a));
        for (int i = 2; i <= M * 2 + 1; ++i)
            a[i][i] = 1;
    }
}A;

inline void addEdge (int u, int v) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
}

inline matrix quick_pow (matrix x, ll p) {
    matrix ans;
    ans.init();
    while (p) {
        if (p & 1)
            ans = (ans * x) % MOD;
        x = (x * x) % MOD;
        p >>= 1;
    }
    return ans;
}

int main () {
    read(N), read(M), read(t), read(S), read(T);
    S++, T++;
    int u, v;
    for (int i = 1; i <= M; ++i) {
        read(u), read(v);
        u++, v++;
        addEdge(u, v), idx[u][v] = cap;
        addEdge(v, u), idx[v][u] = cap;
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = head[i]; j; j = nxt[j]) {
            for (int k = head[i]; k; k = nxt[k])
                if (k != j) {
                    A.a[j ^ 1][k] = 1;
                }
        }
    }
    A = quick_pow(A, t - 1);
    for (int i = head[S]; i; i = nxt[i])
        f[i] = 1;
    ll res = 0;
    for (int i = 2; i <= M * 2 + 1; ++i) {
        for (int j = 2; j <= M * 2 + 1; ++j) {
            (g[i] += f[j] * A.a[j][i] % MOD) %= MOD;
        }
    }
    for (int i = head[T]; i; i = nxt[i])
        (res += g[i ^ 1]) %= MOD;
    printf("%lld\n", res);
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注