博客

题意:


给定一张无向图，每条路的长度都是1，没有自环，可能有重边，给定起点与终点，求从起点走t步到达终点的方案数。

每一步走的时候要求不能走上一条刚刚走的路。


解析:


显然需要搞出个矩阵之后矩乘。

然而这题的要求就很烦，要不然就是SB题了2333.

但是我们可以换一个想法来做。

题目要求不走上一条来的边，况且边的数量还很少，所以我们可以考虑将矩阵构造成从一条边走到另一条边的方案数。

这样的话我们避免走上一条来的路就很简单的能判断了。

构造出初始矩阵后，我们求该矩阵的t-1次方。

然后再用起点走一步能到的边的矩阵乘以该矩阵。

之后起点到链接终点的边的所有方案数之和即为答案。


代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 45989
#define N 22
using namespace std;
int n,m,t,a,b;
struct Matrix
{
    int map[N*6][N*6];
    void clear(){memset(map,0,sizeof(map));}
    friend Matrix operator * (Matrix &a,Matrix &b)
    {
        Matrix ret;
        for(int i=0;i<=2*m;i++)
        {
            for(int j=0;j<=2*m;j++)
            {
                ret.map[i][j]=0;
                for(int k=0;k<=2*m;k++)
                {                   
                    ret.map[i][j]=ret.map[i][j]+a.map[i][k]*b.map[k][j]%mod;
                }
                ret.map[i][j]%=mod;
            }
        }
        return ret;
    }
    friend Matrix operator ^ (Matrix &a,int b)
    {
        Matrix ret;
        ret.clear();
        for(int i=0;i<=m*2;i++)ret.map[i][i]=1;
        while(b)
        {
            if(b&1)ret=ret*a;
            a=a*a;
            b>>=1;
        }
        return ret;
    }
}ori,base;
int head[N],cnt;
struct node
{
    int from,to,next;
}edge[N*6];
void init()
{
    memset(head,-1,sizeof(head));
    cnt=1;
}
void edgeadd(int from,int to)
{
    edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];
    head[from]=cnt++;
}
int main()
{
    init();
    scanf("%d%d%d%d%d",&n,&m,&t,&a,&b);
    a++,b++;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x++,y++;
        edgeadd(x,y),edgeadd(y,x);
    }
    for(int i=head[a];i!=-1;i=edge[i].next)
        base.map[0][i]++;
    for(int i=1;i<cnt;i++)
    {
        int x=edge[i].from,y=edge[i].to;
        for(int j=head[y];j!=-1;j=edge[j].next)
        {
            if(j!=(i+((i&1)?1:-1)))
                ori.map[i][j]++;
        }
    }
    ori=ori^(t-1);
    base=base*ori;
    int sum=0;
    for(int i=1;i<cnt;i++)
    {
        if(edge[i].to==b)
            sum=(sum+base.map[0][i])%mod;
    }
    printf("%d\n",sum);
}