P5789 可乐

## 矩阵快速幂 ### 原创思路还是要感谢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; }