迷路

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1805 字
N个点的有向图，第i行第j列为1~9表示i到
一本通
练习
正文

/*
原题：T1647「一本通 6.5 练习 3」迷路
题意：N 个点的有向图，第 i 行第 j 列为 1~9 表示 i 到 j 的耗时、为 0 表示无边；
求从 1 号点到 N 号点恰好耗时 T 的路径条数，答案对 2009 取模。
思路：边权在 1~9，把每个点 i 拆成 9 个状态记录「已经过的时间」：
从 (i,k) 到 (i,k+1) 表示再过 1 单位但不移动，对权为 w 的边 i->j 连 (i,w)->(j,1)。
这样每条转移都恰好耗时 1，走 i->j 需先沿内部链走 w-1 步再跳一次，合计正好 w。
于是答案就是邻接矩阵 T 次幂中由 (1,1) 到 (N,1) 的元素。
复杂度：时间 O((9N)^3·log T)，空间 O((9N)^2)
易错点：1) 权为 w 的边要从第 w 个状态连出，不能从第 1 个状态连出，否则多扣时间；
2) 目标状态是 (N,1) 而不是第 9 个状态；
3) 内部链只连 1~8，第 9 个状态不再向后连。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=2009;
int idx(int u,int k){
    return (u-1)*9+(k-1);
}
vector<vector<long long>> mul(const vector<vector<long long>>& x,const vector<vector<long long>>& y,int n){
    vector<vector<long long>> r(n,vector<long long>(n,0));
    for(int i=0;i<n;i++){
        for(int k=0;k<n;k++){
            if(x[i][k]==0){
                continue;
            }
            for(int j=0;j<n;j++){
                r[i][j]=(r[i][j]+x[i][k]*y[k][j])%MOD;
            }
        }
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    long long T;
    cin>>N>>T;
    int sz=N*9;
    vector<vector<long long>> base(sz,vector<long long>(sz,0));
    for(int u=1;u<=N;u++){
        for(int k=1;k<=8;k++){
            base[idx(u,k)][idx(u,k+1)]=1;
        }
    }
    for(int u=1;u<=N;u++){
        string s;
        cin>>s;
        for(int v=1;v<=N;v++){
            int w=s[v-1]-'0';
            if(w>0){
                base[idx(u,w)][idx(v,1)]=1;
            }
        }
    }
    vector<vector<long long>> r(sz,vector<long long>(sz,0));
    for(int i=0;i<sz;i++){
        r[i][i]=1;
    }
    while(T>0){
        if(T&1){
            r=mul(r,base,sz);
        }
        base=mul(base,base,sz);
        T>>=1;
    }
    cout<<r[idx(1,1)][idx(N,1)]%MOD<<"\n";
    return 0;
}
迷路

正文

一本通·提高篇的其它内容
