题解：P2151

wallace_QwQ · 2025-01-27 21:51:08 · 题解

前言：

辅导机构练习比赛把这道题的 m 开到了丧心病狂的 5 \times 10^5。

蒟蒻惨遭薄纱，于是就有了这么一篇加强版的题解。

注：以下所有下标均经过加1处理。

考虑到加强版后的 m 达到了 5 \times 10^5，那么原来本题拆边的做法显然是无法通过的，所以还是得在 n 上动脑筋。

我们设 f_{i,j,t} 表示在 t 时刻最后经过的两个节点为 i,j 以及 g_{i,j} 表示从 i 到 j 的边的数量。

这样会有f_{i,j,t}=g_{i,j}\sum_k(f_{k,i,t-1})-f_{j,i,t-1}。

显然不好用矩阵快速幂直接维护。

那么，我们不妨再令 A_{i,t}=\sum_kf_{k,i,t} 即表示 t 时刻在 i 节点的路径数， B_{i,t}=\sum_kf_{i,k,t} 即表示在 t-1 时刻在 i 节点走下一步的方案数。

经过推导我们得到：

• A_{i,t}=A_{k,t-1}\sum_kg_{k,i}-B_{i,t-1}
• B_{i,t}=A_{i,t-1}\sum_k(g_{i,k}-1)

那么答案即为 A_{ed,t}。

然后就可以愉快地矩阵加速了。

什么？

你问这玩意怎么矩阵加速？

首先我们发现 t 这一维是可以滚掉的。

然后我们建立一个 1\times 2n 的矩阵 F，其中第 1\sim n 列存 A，第 n+1\sim 2n 存 B。

我们再根据刚刚推导的转移关系构建转移矩阵 T。

如何构建？

将滚调 t 这一维的 A,B 转化成 1\times n 的矩阵，刚刚的推导关系再化简一下：

• A_{1,i}=A_{1,k}\sum_kg_{k,i}-B_{1,i}
• B_{1,i}=A_{1,i}\sum_k(g_{i,k}-1)

直观但不严谨的表示：

• A'=A\times g + B\times(-1)
• B'=A\times (g-1)+B\times0

如果还是没懂，请看下图 T 矩阵的具体内容：

总复杂度：O(n^3\log t)

代码已经过可读性修改：

void solve(){
    cin>>n>>m>>t>>st>>ed; 
    st++,ed++;
    for1(i,1,m){
        int u,v;
        cin>>u>>v;
        u++,v++;
        g[u][v]++,g[v][u]++;
    }
    T.row=T.col=n*2;
    for1(i,1,n){
        T.t[i+n][i]=T.t[i][i+n]=-1;
        for1(j,1,n)
            T.t[i][i+n]+=g[i][j],T.t[i][j]=g[i][j];
    }
    F.row=1,F.col=n*2;
    for1(i,1,n)
        F.t[1][i]+=g[st][i],F.t[1][st+n]+=g[st][i];
    F=F*(T^(t-1));
    cout<<F.t[1][ed];
    return ;
}