q234rty's Blog

看起来像个裸矩乘。。

但是题目中有这样一句话：

但是同时HH又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。

以点作为状态的算法很难处理这个条件，我们考虑以边作为状态。

只要在建矩阵的时候判断一下，不要从一条边直接走到它的反向边就可以了。

#include <iostream>
#include <cstring>
#include <cassert>
using namespace std;
typedef long long ll;
const int mod=45989;
struct matrix{
    int r,c;
    ll a[121][121];
    matrix(int r,int c){
        this->r=r;
        this->c=c;
        memset(a,0,sizeof(a));
    }
    ll * operator[](int p){
        return a[p];
    }
    matrix operator =(const matrix& rhs){
        //puts("WTF");
        assert(r==rhs.r && c==rhs.c);
        memcpy(a,rhs.a,sizeof(a));
        return *this;
    }
    matrix operator *(matrix& rhs){
        assert(c==rhs.r);
        //puts("WTF");
        matrix res(r,rhs.c);
        //puts("WTF");
        for(int i=0;i<r;i++)
            for(int j=0;j<rhs.c;j++)
                for(int k=0;k<c;k++)
                    (res[i][j]+=((a[i][k]*rhs[k][j])%mod))%=mod;
        //puts("WTF");
        return res;
    }
    matrix operator *=(matrix& rhs){
        return *this=(*this)*rhs;
    }
};
matrix power(const matrix& mat,ll b){
    //puts("WTF");
    matrix ret(mat.r,mat.c);
    matrix t(mat.r,mat.c);
    t=mat;
    //puts("line 48");
    for(int i=0;i<mat.r;i++)
        ret[i][i]=1;
    while(b){
        //puts("WTF");
        if (b%2)
            ret=ret*t;
        t=t*t;
        b/=2;
    }
    return ret;
}
struct edge{
    int from,to;
};
edge e[121];
int main(){
    int n,m,t,a,b;
    cin >> n >> m >> t >> a >> b;
    a++,b++;
    int cur=0;
    for(int i=1;i<=m;i++){
        int x,y;
        cin >> x >> y;
        x++,y++;
        e[cur++]=(edge){x,y};
        e[cur++]=(edge){y,x};
    }
    matrix mt(cur,cur);
    for(int i=0;i<cur;i++){
        for(int j=0;j<cur;j++){
            if (e[i].to==e[j].from && i!=(j^1))
                mt[i][j]++;
        }
    }
    mt=power(mt,t-1);
    int ans=0;
    for(int i=0;i<cur;i++)
        for(int j=0;j<cur;j++)
            if (e[i].from==a && e[j].to==b)
                (ans+=mt[i][j])%=mod;
    cout << ans;
}