题解 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;
}