洛谷2151 [SDOI2009]HH去散步(矩阵快速幂,边点互换)

题意:HH有个一成不变的习惯,喜欢饭后百步走。所谓百步走,就是散步,就是在一定的时间 内,走过一定的距离。 但是同时HH又是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人,所以他每天走过的路径都不完全一样,他想知道他究竟有多 少种散步的方法。现在给你学校的地图(假设每条路的长度都是一样的都是1),问长度为t,从给定地 点A走到给定地点B共有多少条符合条件的路径。

输入格式:第一行:五个整数N,M,t,A,B。其中N表示学校里的路口的个数,M表示学校里的 路的条数,t表示HH想要散步的距离,A表示散步的出发点,而B则表示散步的终点。

接下来M行,每行一组Ai,Bi,表示从路口Ai到路口Bi有一条路。数据保证Ai != Bi,但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N − 1。 同一行内所有数据均由一个空格隔开,行首行尾没有多余空格。没有多余空行。 答案模45989。 

输出格式:一行,表示答案。

分析:考虑如何将双向边变得有差异。把边看成点,正向x->y建一条有向边,反向y->x建一条有向边,如果边E1:x->y , 边E2:y->z 则E1向E2连一条边;这样如何处理走回来的情况呢??只要同一条边拆出来的两个点不相互连边即可;

注意要构造一个虚拟点编号0,它连向点A,为单向边,该边编号为1。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int mod = 45989;

int n,m,t,a,b,x,y,goal,cnt = 1;
int head[60],to[10000];
vector<int> vt[60];

struct Node{
    int a[200][200];
    Node operator *(const Node &x)const{
        Node ans;
        memset(ans.a,0,sizeof(a));
        for(int i = 1; i <= cnt; ++i)
            for(int t = 1; t <= cnt; ++t)
                for(int k = 1; k <= cnt; ++k)
                    ans.a[i][t] = (ans.a[i][t]+a[i][k]*x.a[k][t]) % mod;
        return ans;
    }
}base,ans;

void quick_pow(int n){
    ans = base;
    while(n){
        if(n&1)  ans = ans*base;
        base = base*base;  n >>= 1;
    }
}

int main(){
    scanf("%d%d%d%d%d",&n,&m,&t,&a,&b);
    ++a, ++b;  to[1] = a;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d",&x,&y);    
        ++x, ++y;
        //cnt表示当前边的编号,to数组是有向边的终点
        to[++cnt] = y, vt[x].push_back(cnt);
        to[++cnt] = x, vt[y].push_back(cnt);
    }
    for(int i = 1; i <= cnt; ++i){
        int u = to[i];
        for(auto &x : vt[u]){
            // 如果两条边是来自同一条边,跳过
            if(x == (i^1))  continue;
            base.a[i][x] = 1;
        }
    }
    quick_pow(t-1);
    for(int i = 1; i <= cnt; ++i)   
        if(to[i] == b)  goal = (goal+ans.a[1][i]) % mod;
    printf("%d",goal);
    return 0;
}

 

上一篇:插槽


下一篇:格式化时间要小心,HH hh不一样