bzoj 1297 [SCOI2009]迷路-白红宇

bzoj 1297 [SCOI2009]迷路

阅读量：6930 次

发布时间：2019-06-27

本文共 1324 字，大约阅读时间需要 4 分钟。

题目：

用emacs打的第二道题目！

其实很简单。就是拆点。然后就和poj3613一样了。

把边拆成权值个数的点。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int N=1015,mod=2009;int n,tot,T;struct Matrix{  int a[N][N];  Matrix(){memset(a,0,sizeof a);}  Matrix operator* (const Matrix &b)const  {    Matrix c;    for(int i=0;i<=tot;i++)      for(int k=0;k<=tot;k++)    for(int j=0;j<=tot;j++)      (c.a[i][j]+=(a[i][k]*b.a[k][j]))%=mod;    return c;  }}r,ans;int main(){  scanf("%d%d",&n,&T);tot=n-1;int x;  for(int i=0;i
         
          >=1;    }  printf("%d\n",ans.a[0][n-1]);  return 0;}

View Code

但是WA了。可能是数组太大，爆栈了什么的。

其实应该是把点拆成9个点，自己向自己的第一个点走的距离表示连向自己的边的权值。

#include
     
      #include
      
       #include
       
        using namespace std;const int mod=2009,base=9;int n,tot,T;struct Matrix{  int a[95][95];  Matrix(){memset(a,0,sizeof a);}  Matrix operator * (const Matrix &b)const  {    Matrix c;    for(int i=1;i<=tot;i++)      for(int k=1;k<=tot;k++)    for(int j=1;j<=tot;j++)      (c.a[i][j]+=a[i][k]*b.a[k][j])%=mod;    return c;  }}ans,r;int main(){  scanf("%d%d",&n,&T);int x;tot=n*base;  for(int i=0;i
        
         >=1;    }  printf("%d\n",ans.a[1][(n-1)*base+1]);  return 0;}