SCOI2009迷路

梦里梦外; 2021-12-03 11:13 235阅读 0赞

当初学矩阵幂的时候弃掉了，那时候只会用矩阵优化递推，碰到这种图论的瞬间躺地。

昨天听学长的课，有一道例题，在边权为一的图上求从某点到某点的路径方案数，只要对邻接矩阵跑qpow就完事了。

于是自己画了个小图，手跑矩阵，发现是真的，开始思考why。

其实矩阵幂感觉和floyed很像，c\[i\]\[j\]=∑a\[i\]\[k\]\*b\[k\]\[j\]，k就像是floyed中的断点，每次进行一次操作就好像走了一步，那么就会有方案数的改变，a到b走两步，可以由k1、k2、k3……过去，那矩阵幂就把这个过程加速了。

至于这种边权不为1的，可以拆成9个点，除了第一个是实点，别的都是虚点，各个点直接连单向边，权为1，表示可以用一的贡献过去，然后有权值直接从i的第val个虚点指向j的第1个点，这样就和原问题等价了。

剩下的就是qpow和最后输出谁了，自己想想，不会的看代码在想想。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<set>
    #include<map>
    using namespace std;
    const int P=2009;
    int n,k;
    char ch[300];
    int cal(int i,int j){
        return (i-1)*9+j;
    }
    struct Matrix{
        int x[120][120];
        friend Matrix operator * (Matrix a,Matrix b){
            Matrix c;
            memset(c.x,0,sizeof(c.x));
    //        c.debug();
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    for(int k=1;k<=n;k++)
                        c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%P;
            return c;
        }
        void add(int a,int b){
            x[a][b]=1;
            return ;
        }
        void ench(){
            for(int i=1;i<=n;i++)
                x[i][i]=1;
            return ;
        }
        void debug(){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++)
                    cout<<x[i][j]<<" ";
                cout<<endl;
            }
        }
        void put(){
            printf("%d",x[1][n-8]);
            return ;
        }
    }a;
    void qpow(int k){
        Matrix b,c;
        c.ench();
    //    cout<<endl;
    //    c.debug();
        b=a;
        for(;k;k>>=1,b=b*b)
            if(k&1) c=c*b;
        a=c;
    }
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            for(int j=1;j<9;j++)
                a.add(cal(i,j),cal(i,j+1));
            scanf("%s",ch+1);
            for(int j=1;j<=n;j++){
                if(ch[j]-'0'==0) continue;
                a.add(cal(i,ch[j]-'0'),cal(j,1));
            }
        }n*=9;
    //    a.debug();
        qpow(k);
    //    cout<<endl;
    //    a.debug();
        a.put();
        return 0;
    }

转载于:https://www.cnblogs.com/Yu-shi/p/11202927.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211203/4d18adcb6b3e443a9f4b975285671054.png