BZOJ1875: [SDOI2009]HH去散步 图上边矩乘

这道题十分的坑……

我作为一只连矩乘都不太会的渣渣看到这道题就只能神搜了…..

首先说一下普通的矩乘求方案，就是高出邻接矩阵然后一顿快速幂…..

矩乘一般就是一些秘制递推…..

再说一下这道题，我们可以看出这小骚题有个条件就是说，不能立刻回头，这就不能用以往的了，以往的前后顺序无关，在矩阵里放的是：f[i][j]就是说第i个状态可以由第j个状态转移而来，那么我们可以看出若这个边为无向边，那么对于->*来说这个->东西可以无脑转移到*，因为*是->的合法状态也是唯几合法状态…..

最后的答案把->到B的加起来就好了…….

#include<cstdio>

#include<cstring>

#define N 25

#define M 65

#define P 45989

using namespace std;

inline int read()

{

     int sum=;

     char ch=getchar();

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

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

     {

         sum=(sum<<)+(sum<<)+ch-'';

         ch=getchar();

     }

     return sum;

}

int a[M<<][M<<],b[M<<];

int n,m,T,A,B;

struct Tr

{

    int to,next,id;

}c[M<<];

int head[N],t;

inline void add(int x,int y)

{

    c[++t].to=y;

    c[t].next=head[x];

    c[t].id=t;

    head[x]=t;

}

bool En[M<<];

inline void  look()

{

    printf("LET US SEE B\n");

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

     printf(" %d ",b[i]);

    printf("\n");

}

inline void Init()

{

     n=read(),m=read(),T=read(),A=read()+,B=read()+;

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

     {

        int x=read()+,y=read()+;

        add(x,y),add(y,x);

     }

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

     {

         for(int i=head[x];i;i=c[i].next)

         {

             int y=c[i].to;

             if(y==B)En[c[i].id]=;

             int caocaocao=;

             for(int j=head[y];j;j=c[j].next)

             {

                 if(c[j].to==x)

                   caocaocao++;

                 if(c[j].to!=x||(c[j].to==x&&caocaocao!=))

                   a[c[j].id][c[i].id]=;

             }

         }

     }

     for(int i=head[A];i;i=c[i].next)

      b[c[i].id]=;

}

int temp[M<<][M<<],d[M<<];

inline void up()

{

      memset(d,,sizeof(d));

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

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

        d[i]+=a[i][j]*b[j]%P;

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

       b[i]=d[i]%P;

}

inline void multi()

{

      memset(temp,,sizeof(temp));

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

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

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

         temp[i][j]+=a[i][k]*a[k][j]%P;

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

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

        a[i][j]=temp[i][j]%P;

}

inline void work()

{

      T=T-;

      while(T)

      {

          //look();

          if(T&)up();

          T>>=;

          multi();

      }

      int ans=;

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

       if(En[i])

        ans+=b[i];

      ans%=P;

      printf("%d",ans);

}

int main()

{

    Init();

    if(T==)

    {

      if(A==B)printf("");

      else printf("");

      return ;

    }

    work();

    return ;

}