AC日记——[SDOI2009]HH去散步 洛谷 P2151

[SDOI2009]HH去散步

思路；

　　矩阵快速幂递推（类似弗洛伊德）；

　　给大佬跪烂～～

代码：

#include <bits/stdc++.h>

using namespace std;

#define mod 45989

struct MatrixType {

    int n,m,ai[][];

    MatrixType(int n_,int m_)

    {

        n=n_,m=m_;

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=m;j++)ai[i][j]=;

        }

    }

    MatrixType operator*(const MatrixType pos)const

    {

        MatrixType res(n,pos.m);

        for(int i=;i<=res.n;i++)

            for(int j=;j<=res.m;j++)

                for(int v=;v<=m;v++)

                    res.ai[i][j]=(res.ai[i][j]+ai[i][v]*pos.ai[v][j])%mod;

        return res;

    }

};

int n,m,t,a,b,cnt=-,E[],V[],head[];

bool ma[][];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'')Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

MatrixType poww(MatrixType x,MatrixType y,int e)

{

    while(e)

    {

        if(e&) x=x*y;

        y=y*y,e>>=;

    }

    return x;

}

int main()

{

    memset(head,-,sizeof(head));

    in(n),in(m),in(t),in(a),in(b);

    int u,v;

    for(int i=;i<=m;i++)

    {

        in(u),in(v);

        E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;

        E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;

    }

    MatrixType bi(cnt,cnt);

    for(int i=;i<=cnt;i++)

    {

        for(int v=head[V[i]];v!=-;v=E[v])

        {

            if(v!=(i^)) bi.ai[i][v]++;

        }

    }

    MatrixType ai(,cnt);

    for(int i=head[a];i!=-;i=E[i]) ai.ai[][i]++;

    MatrixType ans=poww(ai,bi,t-);

    int ans_=;

    for(int i=;i<=ans.m;i++) if(V[i]==b)ans_=(ans_+ans.ai[][i])%mod;

    printf("%d",ans_);

    return ;

}