洛谷 P3758 【TJOI2017】可乐 题解

洛谷 P3758 【TJOI2017】可乐 题解

xiaoh 2020-4-6

题意

给定一张有nn个点,mm条边的简单无向图(1n30,1m1001\leq n\leq 30,1\leq m\leq 100),有一个机器人初始在11号点,每一秒可以选择停留在原地,延一条边走一步或自爆,求tt秒后总的行为的方案数.(1t1061\leq t\leq 10^6)

题解

考虑进行dpdp.记fi,jf_{i,j}为目前在ii点,走了jj步的总方案数,则可得如下转移方程:

fi,j=kifk,j1f_{i,j}=\sum_{k可以直达i}f_{k,j-1}

那么自爆怎么办呢?我们可以把自爆理解成为一个点,这个点只进不出,加一个点连单向边即可.同样的,停留在原地可以理解为自环.

发现可以用滚动数组来优化空间,目前的时间复杂度为O(mt)O(mt),可能加了一口新鲜的氧气就过了显然由于常数的原因无法通过.

但是我们发现,本题是常系数递推,重点是,nn还贼小!于是我们想到了矩阵快速幂优化递推.我们将上述的边(包括自爆和停留的边)建成一个邻接矩阵,即为AA.则将fif_i也视为一个矩阵时,两个每相乘一次即为每多走一步当前的情况,于是乎用熟悉的矩阵快速幂优化即可.时间复杂度O(n3logt)O(n^3\log t).这回总能过去了吧QAQ

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=35;
const int mod=2017;
int n,m,t;
struct Mat{//矩阵类
public:
    int a[MAXN][MAXN];
    friend Mat operator *(const Mat &x,const Mat &y)
    {
        Mat ret;
        for(int i=1;i<=n+1;i++)
        for(int j=1;j<=n+1;j++) ret.a[i][j]=0;
        for(int i=1;i<=n+1;i++)
        for(int j=1;j<=n+1;j++)
        for(int k=1;k<=n+1;k++) ret.a[i][j]+=x.a[i][k]*y.a[k][j],ret.a[i][j]%=mod;
        return ret;
    }
}a;//a为初始的邻接矩阵
Mat pow(int k)//矩阵快速幂
{
    if(k==1) return a;
    Mat tmp=pow(k>>1);
    tmp=tmp*tmp;
    if(k&1) tmp=tmp*a;
    return tmp;
}
int ans=0;
int main()
{
    read(n),read(m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        read(u),read(v);
        a.a[u][v]=a.a[v][u]=1;//按照条件连边
    }
    read(t);
    for(int i=1;i<=n;i++) a.a[n+1][i]=1;//建自爆的边
    for(int i=1;i<=n+1;i++) a.a[i][i]=1;//建停留的边
    Mat cur=pow(t);
    for(int i=1;i<=n+1;i++) ans+=cur.a[i][1],ans%=2017;//统计答案
    write(ans),putchar('\n');
	return 0;
}