bzoj 4887 洛谷 5789&3758 [TJOI2017]可乐 题解

发表于 | 更新于 | 阅读次数：
本文字数： 992 字 | 阅读时长 ≈ 5 分钟

（PS：洛谷上5789是加强版，3758是可以dp水过的原版）
（本文讲最优做法，能通过加强版的）

题意简述

有$n$个点$m$条边的无向图，你有一个机器人，从点$1$开始走。每次可以：停留在原地，自爆（就不能继续走了），选一个相邻的点继续走。边珂以重复经过。问你走$k$步有多少种情况。答案对$2017$取膜。

（最高数据）$n,m<=100,k<=1e9$。

思路

停留在原地，我们给每个点加一个自环即珂。
自爆的话，我们加入一个新的$E$（设其编号$n+1$即珂）。对于原图的每一个点，都向$E$连一条有向边。$E$就表示一个爆炸的状态：每个点都可以爆炸，爆炸完就回不去了（边是有向的，去了就回不来了）。

然后我们保存一个邻接矩阵$G$。我们发现，$G[u][v]=1$，表示$u$珂以一步走到$v$。

那么$G^k$（矩阵快速幂）表示什么意义呢？容易得到，它表示：走$k$步，珂以经过重复的边，图的连通方案。$G^k[u][v]$表示$u,v$之间长度为$k$的路径的条数（边能重复经过）。

那么我们根据上面的建图方式，建出邻接矩阵，然后矩阵快速幂求$k$次方，$G[1][1]+G[1][2]+…+G[1][n+1]$（$n+1$就是点$E$），就是机器人走$k$步的所有方案数了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 122
    #define mod 2017
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class Matrix//square matrix
    {
        #define S 122//changeable
        private:
            int a[S][S];
        public:
            //variable list
            int n;//size
            //initialization
            Matrix()
            {
                memset(a,0,sizeof(a));
                n=0;
            }
            Matrix(int _n)
            {
                memset(a,0,sizeof(a));
                n=_n;
            }
            Matrix(int _n,int _x)
            {_x%=mod;
                n=_n;
                for(int i=0;i<S;++i)
                {
                    for(int j=0;j<S;++j)
                    {
                        a[i][j]=_x;
                    }
                }
            }
    
            //get value
            int* operator[](int i)
            {
                return *(a+i);
            }
    
            //set value
            void Set(int x)
            {x%=mod;
                for(int i=0;i<S;++i)
                {
                    for(int j=0;j<S;++j)
                    {
                        a[i][j]=x;
                    }
                }
            }
            void Identity()
            {
                memset(a,0,sizeof(a));
                for(int i=0;i<S;++i)
                {
                    a[i][i]=1;
                }
            }
            #undef S //5
    };
    Matrix operator*(Matrix x,Matrix y)
    {
        Matrix ans(x.n,0);
        int n=ans.n;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if (x[i][j])
                {
                    for(int k=1;k<=n;++k)
                    {
                        ans[i][k]+=x[i][j]*y[j][k];
                        ans[i][k]%=mod;
                    }
                }
            }
        }
        return ans;
    }
    Matrix operator^(Matrix x,int p)
    {
        Matrix ans(x.n,1);
        ans.Identity();
        while(p)
        {
            if (p&1) ans=ans*x;
            x=x*x,p>>=1;
        }
        return ans;
    } //到这里都是矩阵

    int n,m,t;
    Matrix G(101,0); //矩阵开n+1个大小
    void Input()
    {
        Rd(2,&n,&m);
        F(i,1,m)
        {
            int u,v;Rd(2,&u,&v);
            G[u][v]=G[v][u]=1;
        }
        F(i,1,n+1) G[i][i]=G[i][n+1]=1; 
        //G[i][i]是停留在原地的边，G[i][n+1]是自爆的边
    }

    void Soviet()
    {
        R1(t); //名字不太一样...t就是上面说的k，抱歉
        G=G^t;
        int ans=0;
        F(i,1,n+1) ans+=G[1][i],ans%=mod;
        printf("%d\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w