SDOI2009[HH去散步]

动态规划，矩阵优化。

动规方程见注释。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-25

DESCRIPTION:

山东2009年省选 HH去散步

*/

#include <iostream>

#include <string.h>

using namespace std;

 

const int MAXN=20;

const int MAXM=60;

const int MODER=45989;

int N,M,A,B;

long long int t;

int a[MAXM*2],b[MAXM*2];

typedef unsigned int matrix[MAXM*2][MAXM*2];

int K;

matrix mA,mB,mBB,mC;

void mul(matrix A,matrix B,matrix C)

{

     for (int i=0;i<K;i++)

         for (int j=0;j<K;j++)

         {

             C[i][j]=0;

             for (int k=0;k<K;k++)

                 C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MODER;

         }

}

void power(matrix A,long long int n,matrix B)

{

     matrix a,b,ab,aa;

     matrix* bp=&b;

     matrix* ap=&a;

     matrix* abp=&ab;

     matrix* aap=&aa;

     matrix* swap;

     memcpy((*ap),A,sizeof(matrix));

     memset((*bp),0,sizeof(matrix));

     for (int i=0;i<K;i++) (*bp)[i][i]=1;

     while (n)

     {

           if (n&1)

           {

              mul(*bp,*ap,*abp);

              swap=bp;

              bp=abp;

              abp=swap;

           }

           mul(*ap,*ap,*aap);

           swap=ap;

           ap=aap;

           aap=swap;

           n>>=1;

     }

     memcpy(B,*bp,sizeof(matrix));

}

int main()

{

    cin>>N>>M>>t>>A>>B;

    for (int i=0;i<M;i++)

        cin>>a[i]>>b[i],

        a[i+M]=b[i],b[i+M]=a[i];

    //f[T][EDGE]表示走了T步,在最后走的是EDGE的方案数

    //f[1][EDGE]=1 v(EDGE)=A

    //f[T][EDGE]=sum{f[T-1][EDGE’];v(EDGE)=u(EDGE’) and EDGE!=EDGE’的反向边}

    K=M*2;

    for (int i=0;i<K;i++)

        if (a[i]==A) mA[0][i]=1;

    for (int i=0;i<K;i++)

        for (int j=0;j<K;j++)

            if (b[i]==a[j]&&i!=j+M&&j!=i+M)

               mB[i][j]=1;

    power(mB,t-1,mBB);

    for (int i=0;i<1;i++)

        for (int j=0;j<K;j++)

            for (int k=0;k<K;k++)

                mC[i][j]=(mC[i][j]+mA[i][k]*mBB[k][j])%MODER;

    int answer=0;

    for (int i=0;i<K;i++)

        if (b[i]==B) answer=(answer+mC[0][i])%MODER;

    cout<<answer<<endl;

}