题解 P3758 【[TJOI2017]可乐】

asuldb · 2018-10-05 14:16:37 · 个人记录

首先邻接矩阵用来做矩阵乘法还是非常有意义的

如果一个邻接矩阵A做了k次矩阵乘法，那么A_{i,j}就表示从i到j走k步的方案数

这道题不一样的就是可以在与原地停留还有自爆

原地停留的话那就自己向自己连一条边，那就可以自己来回走了

自爆的话就设置一个虚点n+1，让所有的点向n+1连边，之后n+1向自己连边，一旦到了n+1那么就只能在n+1来回走，于是就可以区分出在不同时间自爆的方案

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 35
const int mod=2017;
int ans[maxn][maxn],a[maxn][maxn];
int n,m,T;
inline int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
inline void did_a()
{
    int mid[maxn][maxn];
    for(re int i=1;i<=n+1;i++)
        for(re int j=1;j<=n+1;j++)
            mid[i][j]=a[i][j],a[i][j]=0;
    for(re int i=1;i<=n+1;i++)
        for(re int j=1;j<=n+1;j++)
            for(re int p=1;p<=n+1;p++)
                {
                    a[i][j]+=mid[i][p]*mid[p][j];
                    if(a[i][j]>mod) a[i][j]%=mod;
                }
}
inline void did_ans()
{
    int mid[maxn][maxn];
    for(re int i=1;i<=n+1;i++)
        for(re int j=1;j<=n+1;j++)
            mid[i][j]=ans[i][j],ans[i][j]=0;
    for(re int i=1;i<=n+1;i++)
        for(re int j=1;j<=n+1;j++)
            for(re int p=1;p<=n+1;p++)
                {
                    ans[i][j]+=a[i][p]*mid[p][j];
                    if(ans[i][j]>mod) ans[i][j]%=mod;
                }
}
inline void quick(int b)
{
    while(b)
    {
        if(b&1) did_ans();
        b>>=1;
        did_a();
    }
}
int main()
{
    n=read(),m=read();
    int x,y;
    for(re int i=1;i<=m;i++)
        x=read(),y=read(),a[x][y]=a[y][x]=1;
    for(re int i=1;i<=n;i++)
        a[i][i]=a[i][n+1]=1;
    a[n+1][n+1]=1;
    for(re int i=1;i<=n+1;i++)
        ans[i][i]=1;
    T=read();
    quick(T);
    int num=0;
    for(re int i=1;i<=n+1;i++)
        num=(num+ans[1][i])%mod;
    std::cout<<num;
    return 0;
}