BZOJ1875 [SDOI2009]HH去散步

2014.12.19 16:29 Fri| 0 visits oi_2015| 2015_刷题日常| Text

Solution

一眼看去,如果没有每一条边不能连续经过两次的限制条件,这就又是一道矩阵乘法的水题。既然不能连续经过两次,那么把边看做点即可。建立初始矩阵的时候判断若两条边的相邻且不互为反向边,则将这两条边之间设为可达。需要注意进行快速幂时只需要自乘t-1次。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 125
#define mod 45989

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]<<' ';
    }
};

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

pair<int,int> p[N];
int n,m,t,a,b,tot,ans;

int main()
{
    cin>>n>>m>>t>>a>>b;
    for(int x,y,i=1;i<=m;i++)
        p[tot++]=pair<int,int>(x=read(),y=read()),
        p[tot++]=pair<int,int>(y,x);
    matrix mat(tot);
    for(int i=0;i<tot;i++)
        for(int j=0;j<tot;j++)
            if(p[i].second==p[j].first&&(i^j)!=1)
                mat.m[i][j]++;
    mat=pow(mat,t-1);
    for(int i=0;i<tot;i++)
        if(p[i].first==a)
            for(int j=0;j<tot;j++)
                if(p[j].second==b)
                    ans=(ans+mat.m[i][j])%mod;
    cout<<ans<<endl;
}