M_sea

洛谷3758 [TJOI2017]可乐
Luogu算法搞出一个邻接矩阵$G$,边权为1。不难发现$G^k$的第$i$行第$j$列的数字含义是从$i$到$j...
扫描右侧二维码阅读全文
03
2018/08

洛谷3758 [TJOI2017]可乐

Luogu

算法

搞出一个邻接矩阵$G$,边权为1。

不难发现$G^k$的第$i$行第$j$列的数字含义是从$i$到$j$经过$k$步的路径方案总数。

那么直接把图建出来,矩阵快速幂搞搞即可。

但是如何处理不动和自爆呢?

不动很简单,搞一个自环即可。

自爆的话,搞一个$0$节点,$0\sim n$都向$0$连一条边即可。这样子保证了自爆后就没有后继了。

细节见代码。

代码

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

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

const int MOD=2017;

struct Matrix {
    int m[50][50];
};

Matrix Mul(Matrix a,Matrix b,int n) {
    Matrix c;
    for (re int i=0;i<=n;i++)
        for (re int j=0;j<=n;j++) {
            c.m[i][j]=0;
            for (re int k=0;k<=n;k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
        }
    return c;
}

Matrix FastPow(Matrix a,int k,int n) {
    Matrix rt;
    for (re int i=0;i<=n;i++)
        for (re int j=0;j<=n;j++) {
            if (i==j) rt.m[i][j]=1;
            else rt.m[i][j]=0;
        }
    while (k) {
        if (k&1) rt=Mul(rt,a,n);
        a=Mul(a,a,n);
        k>>=1;
    }
    return rt;
}

Matrix G;

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=m;i++) {
        int a=read(),b=read();
        G.m[a][b]=G.m[b][a]=1;
    }
    for (re int i=0;i<=n;i++) G.m[i][i]=1;
    for (re int i=1;i<=n;i++) G.m[i][0]=1;
    int t=read();
    G=FastPow(G,t,n);
    int ans=0;
    for (re int i=0;i<=n;i++) ans=(ans+G.m[1][i])%MOD;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 38 PM

发表评论