矩阵 trick 系列 题解

1.AT_dp_r Walk（矩阵+图论）

题意

一个有向图有 $n$ 个节点，编号 $1$ 至 $n$。

给出一个二维数组$A_{\mathrm{1...}n,\mathrm{1...}n}$，若 $A_{i,j}=1$ 说明节点 $i$ 到节点 $j$ 有一条有向边;

若 $A_{i,j}=0$ 则说明节点 $i$ 到节点 $j$ 没有边。

求长度为 $k$ 的路径的方案数。答案模 $10^9+7$。

思路

走动一次路径加 $1$，一个点对所有点遍历一遍。

直接对矩阵 $A$ 快速 $k$ 次幂，求 $\sum data(A)$ 就好了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=111,mod=1e9+7;
ll n,k,ans;
struct matrix
{ll row,col;//行和列ll data[N][N];matrix(ll r,ll c,ll isI){row=r;col=c;memset(data,0,sizeof(data));if(isI){for(int i=1;i<=row;i++)data[i][i]=1;}}
};
matrix operator * (const matrix &a,const matrix &b)
{matrix c(a.row,b.col,0);for(int i=1;i<=a.row;i++)for(int j=1;j<=b.col;j++)for(int k=1;k<=a.col;k++)c.data[i][j]=(c.data[i][j]+a.data[i][k]*b.data[k][j]%mod+mod)%mod;return c;
}
matrix qpow_matrix(matrix a,ll k)
{matrix res(a.row,a.col,1);while(k){if(k&1)res=res*a;a=a*a;k>>=1;}return res;
}
int main()
{scanf("%lld%lld",&n,&k);matrix A(n,n,0);matrix ANS(n,n,0);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lld",&A.data[i][j]);ANS=qpow_matrix(A,k);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans=(ans+ANS.data[i][j])%mod;printf("%lld",ans);return 0;
}

2.SMOJ k边最短路/洛谷 P2886 USACO07NOV Cow Relays G

题意

给定一张 $m$ 条边的无向连通图，求从 $s$ 到 $t$ 经过 $n$ 条边的最短路长度。

$1\le n\le 10^6$，$2\le m\le 100$，$1\le u,v\le 1000$，$1\le w\le 1000$。

思路

改造一下矩阵运算，变成取和最小值即可（变相floyd）。

用矩阵，自觉离散化了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=102,inf=0x3f3f3f3f;
map<ll,ll>mp;
ll tot;
struct matrix
{ll row,col;//行和列ll data[N][N];
};
matrix operator * (const matrix &a,const matrix &b)
{matrix c;memset(c.data,inf,sizeof(c.data));for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++)for(int k=1;k<=tot;k++)c.data[i][j]=min(c.data[i][j],a.data[i][k]+b.data[k][j]);return c;
}
matrix qpow_matrix(matrix a,ll k)
{matrix res;res=a;k--;while(k){if(k&1)res=res*a;a=a*a;k>>=1;}return res;
}
ll n,m,s,t;
int main()
{scanf("%lld%lld%lld%lld",&n,&m,&s,&t);matrix A;memset(A.data,inf,sizeof(A.data));for(int i=1;i<=m;i++){ll w,u,v;scanf("%lld%lld%lld",&w,&u,&v);if(!mp[u])mp[u]=++tot;if(!mp[v])mp[v]=++tot;A.data[mp[u]][mp[v]]=A.data[mp[v]][mp[u]]=w;}A=qpow_matrix(A,n);printf("%lld",A.data[mp[s]][mp[t]]);return 0;
}

3.SMOJ 染色/AT_abc256_g Black and White Stones

题意

有一个正 $n$ 多边形，每条边的长度都是 $d$。

从第 $1$ 个端点开始，每隔 $1$ 个单位距离就放一个小石头，小石头是白色或者黑色。显然，一条边会有 $d+1$ 个小石头。

现在对放石头有一个规定：最后每条边的白色小石头的数量必须相等。问有多少种不同的方案，答案模 $998244353$。

思路

考虑朴素的 dp，设 $f_{i,0/1}$ 表示第 $i$ 条边尾巴是白/黑的方案数。枚举一条边上有 $j\in [0,d+1]$ 条白色石头，那么有：

1. 尾巴是白，可以：
   (1) 白+白白，中间 $d-1$ 个有 $j-2$ 个白乱排。
   (2) 黑+黑白，中间 $d-1$ 个有 $j-1$ 个白乱排。
   $$f_{i,0}=f_{i-1,0}\cdot C_{d-1}^{j-2}+f_{i-1,1}\cdot C_{d-1}^{j-1}$$

2. 尾巴是黑，可以：
   (1) 白+白黑，中间 $d-1$ 个有 $j-1$ 个白乱排。
   (2) 黑+黑黑，中间 $d-1$ 个有 $j$ 个白乱排。
   $$f_{i,1}=f_{i-1,0}\cdot C_{d-1}^{j-1}+f_{i-1,0}\cdot C_{d-1}^j$$

这就很矩阵啊！直接矩阵快速幂优化：
$$\left[\begin{array}{cc}{f}_{i,0}& f_{i,1}\end{array}\right]=\left[\begin{array}{cc}{f}_{i-1,0}& f_{i-1,1}\end{array}\right]\cdot \left[\begin{array}{cc}{C}_{d-1}^{j-2}& C_{d-1}^{j-1}\\ C_{d-1}^{j-1}& C_{d-1}^j\end{array}\right]$$

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5,M=1e4+9,mod=998244353;
ll n,k,ans;
ll fac[M],inv[M];
inline ll read()
{ll s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
inline void write(ll x)
{ if(x==0){putchar('0');return;}ll len=0,k1=x,c[10005];if(k1<0)k1=-k1,putchar('-');while(k1)c[len++]=k1%10+'0',k1/=10;while(len--)putchar(c[len]);
}
struct matrix
{ll row,col;//行和列ll data[N][N];matrix(ll r,ll c,ll isI){row=r;col=c;memset(data,0,sizeof(data));if(isI){for(int i=1;i<=row;i++)data[i][i]=1;}}
};
matrix operator * (const matrix &a,const matrix &b)
{matrix c(a.row,b.col,0);for(int i=1;i<=a.row;i++)for(int j=1;j<=b.col;j++)for(int k=1;k<=a.col;k++)c.data[i][j]=(c.data[i][j]+a.data[i][k]*b.data[k][j]%mod+mod)%mod;return c;
}
matrix qpow_matrix(matrix a,ll k)
{matrix res(a.row,a.col,1);while(k){if(k&1)res=res*a;a=a*a;k>>=1;}return res;
}
ll qpow(ll x,ll k)
{ll res=1;while(k){if(k&1)res=res*x%mod;x=x*x%mod;k>>=1;}return res;
}
void init()
{fac[0]=inv[0]=1;for(int i=1;i<=1e4;i++){fac[i]=fac[i-1]*i%mod;inv[i]=qpow(fac[i],mod-2);}
}
ll C(ll n,ll m)
{if(n<0||m<0||n<m)return 0;return fac[n]%mod*inv[m]%mod*inv[n-m]%mod;
}
int main()
{init();n=read(),k=read();for(int i=0;i<=k+1;i++)//每条边枚举白色个数 {matrix ANS(1,2,0);matrix A(2,2,0);A.data[1][2]=1;matrix B(2,2,0);B.data[1][1]=C(k-1,i-2),B.data[1][2]=B.data[2][1]=C(k-1,i-1),B.data[2][2]=C(k-1,i);ANS=A*qpow_matrix(B,n);ans=(ans+ANS.data[1][2])%mod;}write(ans*2%mod);return 0;
}