[FJOI2018]城市路径问题 矩阵快速幂 求解答

[FJOI2018]城市路径问题

可以帮忙看一下这个代码为什么是对的嘛/为什么可以这么写？

#include
#define ll long long
using namespace std;
const ll P=1e9+7,N=1e3+2;
ll n,q,k,u,v,d;
struct node{
    ll n,m;
    vector> a;
    void res(ll x,ll y,ll k){
        n=x,m=y;
        a.resize(n+1,vector(m+1));
        clear(k);
    }
    void clear(ll x){
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++) a[i][j]=0;
        }
        if(n!=m) return ;
        for(ll i=0;i<=n;i++) a[i][i]=x;
    }
}O,I;
node operator*(node a,node b){
    node ans; 
    ans.res(a.n,b.m,0);
    if(a.m!=b.n) return ans;
    for(ll i=0;i<=a.n;i++){
        for(ll j=0;j<=b.m;j++){
            for(ll k=0;k<=a.m;k++){
                //if(!a.a[i][k]) continue;
                ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j]%P)%P;
            }
        }
    }
    return ans;
}
node qpow(node a,ll b){
    node ans;
    ans.res(a.n,a.m,1);
    while(b){
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&k);
    O.res(n,k,0); 
    I.res(k,n,0);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=k;j++) scanf("%lld",&O.a[i][j]);
        for(ll j=1;j<=k;j++) scanf("%lld",&I.a[j][i]);
    }
    I.a[0][0]=O.a[0][0]=1;
    scanf("%lld",&q);
    while(q--){
        scanf("%lld%lld%lld",&u,&v,&d);
        O.a[v][0]=1;
        node C=O*qpow(I*O,d);//为什么要多乘上一个O？？？
        printf("%lld\n",C.a[u][0]);//答案为什么是这个？？
        O.a[v][0]=0;
    }
    return 0;
}

谢谢！

很明显的矩阵快速幂，发现如果是整个矩阵拿去搞的话 1000^3
就爆炸了，考虑可以把转移拆开，只有第一次和最后一次是 1000 × 20 的转移，中间的都是 20 × 20 的转移，直接做就好了。