首页 / 算法 / P2579 [ZJOI2005]沼泽鳄鱼（邻接矩阵，快速幂）

P2579 [ZJOI2005]沼泽鳄鱼（邻接矩阵，快速幂）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了P2579 [ZJOI2005]沼泽鳄鱼（邻接矩阵，快速幂），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1859字，纯文字阅读大概需要3分钟。

内容图文

题目简洁明了（一点都不好伐）

照例，化简题目

给一张图，每一个时间点有一些点不能走，（有周期性），求从起点第k秒恰好在终点的方案数，可重复，不可停留。

额dp实锤

于是就被打脸了....

有一种东西叫做邻接矩阵，还有一种东西叫做矩阵乘法，bk201大仙曾经讲过，能用邻接矩阵的k次方求这个东西。

那，难度下降了很多了。

但是，对于那周期是3,4,6的鳄鱼怎么办呢？

答案就是：

观察3,4,6，lcm（3,4,6）=12，所以，当k%12==0，鳄鱼们都回到了原状态。

所以，我们就暴力地对于每一种情况建一个邻接矩阵，把不能走的点刨掉，然后把他们依次乘起来（因为不满足交换律）

然后把它给k次方就行了。。。

值得注意的地方：

1、因为点是从0开始，所以根据我的习惯，都加上了1；

2、不满足交换律不满足交换律不满足交换律

3、k不一定整除12，所以在剩余的那一部分要手动乘一下初始矩阵

代码： 

#include<iostream>
#include<cstdio>
#include<cstring>
usingnamespace std;
constint maxn=55;
constint mod=10000;
int m,n,st,en,K,fn;
int map[maxn][maxn];
int unable[maxn][maxn];
struct node
{
    int a[maxn][maxn];
    node()
    {
        memset(a,0,sizeof(a));
    }
}q,w[55];
inline node operator * (const node& x,const node& y)
{
    node z;
    for(int i=1;i<=n;i++)
    {
        for(int k=1;k<=n;k++)
        {
            for(int j=1;j<=n;j++)
            {
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
            }
        }
    }
    return z;
}
node ksm(node x,int y)
{
    node z;
    for(int i=1;i<=n;i++)
    z.a[i][i]=1;
    while(y)
    {
        if(y&1)
        z=z*x;
        x=x*x;
        y>>=1;
    }
    return z;
}

int main()
{
    scanf("%d%d%d%d%d",&n,&m,&st,&en,&K);
    st++;en++;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x++;y++;
        map[x][y]=map[y][x]=1;
    }
    scanf("%d",&fn);
    while(fn--)
    {
        int x;
        scanf("%d",&x);
        for(int j=0;j<x;j++)
        {
            int y;
            scanf("%d",&y);
            y++;
            for(int k=j;k<12;k+=x)
            {
                unable[k][y]=true;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        q.a[i][i]=1;
    }
    for(int i=0;i<12;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                w[i].a[j][k]=(map[j][k]&&!unable[i][k]);
            }
        }
    }
    for(int i=1;i<12;i++)
    {
        q=q*w[i];
    }
    q=q*w[0];
    int k=K/12,t=K-k*12;
    node ans;
    for(int i=1;i<=n;i++)
    {
        ans.a[i][i]=1;
    }
    ans=ans*ksm(q,k);
    for(int i=1;i<=t;i++)
    ans=ans*w[i];
    printf("%d ",ans.a[st][en]);
    return0;
}

（完）

原文：https://www.cnblogs.com/ajmddzp/p/11374728.html

内容总结

以上是互联网集市为您收集整理的P2579 [ZJOI2005]沼泽鳄鱼（邻接矩阵，快速幂）全部内容，希望文章能够帮你解决P2579 [ZJOI2005]沼泽鳄鱼（邻接矩阵，快速幂）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1236695.html

来源：【匿名】