P5789 可乐
one_cell
·
·
题解
矩阵快速幂
原创思路还是要感谢Zhang_RQ神仙
这道题是让我们求在一个n个点，m条边的无向图中从1号点出发，走T步，每一步可以选一种操作，求方案个数。
假设目前在u点，操作有以下3种：
①若存在一条u-v的边，可以从u走到v
②原地不动
③原地自爆
//具体题意可以看https://www.luogu.com.cn/problem/P3758
首先思考如何建图：由于n很小，可以直接邻接矩阵。但原地不动和自爆的情况如何考虑?
①原地不动：等价于往自己连了一个自环，令f[i][i]=1
②原地自爆：我们可以建一个表示自爆的0号城市。则不难发现，只要从1~n这些点都向0号点连一条单向边即可，令f[i][0]=1
暴力搜索一定没有前途，T<=1e9
一. 我们思考如何在图中进行DP：
设f[i][j]表示从i走到j的方案个数,不难发现：f[i][j]=∑f[i][k]*f[k][j]（乘法原理）
则Answer=∑ f[1][i]
那我们跑一遍DP，即可求出答案（有点像Floyd）
注意：这里的DP并不是O（n^3)，我们实际的状态是f[t][i][j]，有一个走了t步的限制
则时间复杂度为O(T*n^2)
T<=1e9，还是不行
思考如何优化
二. 考虑矩阵乘法
我们发现：这里的n，m<=100，但T<=1e9。两个数大小相差甚远
一般这种情况可以考虑如何用矩乘优化
我们观察矩阵乘法的基本形式
matrix operator * (const matrix &A,const matrix &B)
{
matrix C;
C.n=A.n;C.m=B.m;
for(int i=0;i<=C.n;i++)
for(int j=0;j<=C.m;j++)
for(int k=0;k<=A.m;k++)
{
C.c[i][j]=(C.c[i][j]+A.c[i][k]*B.c[k][j])%mod;
}
return C;
}
定理：设现在有一个矩阵A，则A^k含义即是，对于一个A[i][j]，表示从i到j走k步的方案总数
证明：
先抛开矩阵乘法，单纯地思考用DP如何做这道题。
设f[i][j][k]表示从i到j，走了k步的方案个数。
初始化：f[i][j][0]没有意义。我们直接看k=1时的初始化
当k=1时其实就是这张图的邻接矩阵。对于一条边u-v，我们令f[u][v][1]=f[v][u][1]=1
然后考虑状态转移：
f[i][j][k]=∑ f[i][p][k-1]*f[p][j][1]
然后我们发现：k这一维只与k-1维有关系。所以我们可以省略这一维。就变成了f[i][j]=∑ f[i][p]*f[p][j]
然后与朴素的快速幂一比较，发现大同小异，这样问题其实就转化了求A矩阵的T次方
则以上问题就得到了证明
一遍矩阵快速幂，轻松跑过~
详见代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110,mod=2017;
int n,m,T;
struct matrix
{
int n,m,c[N][N];
matrix()
{
n=m=0;
memset(c,0,sizeof(c));
}//初始化
};
matrix operator * (const matrix &A,const matrix &B)
{//自定义函数（乘法）
matrix C;
C.n=A.n;C.m=B.m;
for(int i=0;i<=C.n;i++)
for(int j=0;j<=C.m;j++)
for(int k=0;k<=A.m;k++)
{
C.c[i][j]=(C.c[i][j]+A.c[i][k]*B.c[k][j])%mod;
}
return C;
}//普通的矩阵乘法
matrix ksm(matrix a,int b)
{
matrix ans;
ans.n=ans.m=n;
for(int i=0;i<=n;i++)ans.c[i][i]=1;
//对角矩阵，累计答案
while(b)//与正常的快速幂同理
{
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}//矩阵快速幂
int main()
{
scanf("%d%d",&n,&m);
matrix t;
t.n=n;t.m=n;
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
t.c[u][v]=t.c[v][u]=1;
//原图中的邻接矩阵
}
for(int i=0;i<=n;i++)t.c[i][i]=1;
for(int i=1;i<=n;i++)t.c[i][0]=1;
//连自环和0号城市
scanf("%d",&T);
matrix res=ksm(t,T);//T次方即是答案
int ans=0;
for(int i=0;i<=n;i++)ans=(ans+res.c[1][i])%mod;
//统计答案
printf("%d",ans);
return 0;
}