BZOJ1297 [SCOI2009]迷路

2014.12.19 12:54 Fri| 6 visits oi_2015| 2015_刷题日常| Text

这就是传说中pengzhou看了好久之后说看不懂样例的那道神题……

Solution

样例解释:题目保证可能存在自环 2333

首先可以考虑若能到达的两点间距离均为1,则显然直接建立矩阵f[i][j]表示从i到达j的方案数,自乘K次即可得到答案。注意到这道题中两点间距离最多只有9,那么可以考虑拆点,人为将两点间距离变为1,这样即可建立矩阵,进行矩阵乘法解决问题。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100
#define mod 2009

int n,t;
char str[N][N];

struct matrix
{
    int n,m[N][N];
    matrix(int _n=0):n(_n)
    {
        memset(m,0,sizeof m);
    }
    friend matrix operator *(const matrix &a,const matrix &b)
    {
        matrix re(a.n);
        for(int i=0;i<re.n;i++)
            for(int j=0;j<re.n;j++)
                for(int k=0;k<re.n;k++)
                    re.m[i][j]=(re.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
        return re;
    }
    friend matrix pow(matrix m,int t)
    {
        matrix re(m.n);
        for(int i=0;i<m.n;i++)
            re.m[i][i]=1;
        while(t)
        {
            if(t&1) re*=m;
            m*=m; t>>=1;
        }
        return re;
    }
    matrix &operator *=(const matrix &x){ return *this=*this*x; }
    void print()
    {
        for(int i=0;i<n;i++,puts(""))
            for(int j=0;j<n;j++)
                cout<<m[i][j]<<' ';
    }
};

int main()
{
    cin>>n>>t;
    for(int i=0;i<n;i++)
        scanf("%s",str[i]);
    matrix a(n*9);
    for(int i=0;i<n;i++)
        for(int j=0;j<8;j++)
            a.m[i*9+j][i*9+j+1]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(str[i][j]-'0')
                a.m[i*9+str[i][j]-'0'-1][j*9]=1;
    cout<<pow(a,t).m[0][(n-1)*9]<<endl;
}