注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2009[HH去散步]  

2010-07-25 20:45:52|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

动态规划,矩阵优化。

动规方程见注释。

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;

}

 

  评论这张
 
阅读(815)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018