洛谷 P3758 【TJOI2017】可乐 题解
xiaoh 2020-4-6
题意
给定一张有个点,条边的简单无向图(),有一个机器人初始在号点,每一秒可以选择停留在原地,延一条边走一步或自爆,求秒后总的行为的方案数.()
题解
考虑进行.记为目前在点,走了步的总方案数,则可得如下转移方程:
那么自爆怎么办呢?我们可以把自爆理解成为一个点,这个点只进不出,加一个点连单向边即可.同样的,停留在原地可以理解为自环.
发现可以用滚动数组来优化空间,目前的时间复杂度为,可能加了一口新鲜的氧气就过了显然由于常数的原因无法通过.
但是我们发现,本题是常系数递推,重点是,还贼小!于是我们想到了矩阵快速幂优化递推.我们将上述的边(包括自爆和停留的边)建成一个邻接矩阵,即为.则将也视为一个矩阵时,两个每相乘一次即为每多走一步当前的情况,于是乎用熟悉的矩阵快速幂优化即可.时间复杂度.这回总能过去了吧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;
}