1.AT_dp_r Walk（矩阵+图论）
题意
一个有向图有 n n n 个节点，编号 1 1 1 至 n n n。
给出一个二维数组 A 1... n , 1... n A_{1...n,1...n} A1...n,1...n，若 A i , j = 1 A_{i,j}=1 Ai,j=1 说明节点 i i i 到节点 j j j 有一条有向边;
若 A i , j = 0 A_{i,j}=0 Ai,j=0 则说明节点 i i i 到节点 j j j 没有边。
求长度为 k k k 的路径的方案数。答案模 1 0 9 + 7 10^9+7 109+7。
思路
走动一次路径加 1 1 1，一个点对所有点遍历一遍。
直接对矩阵 A A A 快速 k k k 次幂，求 ∑ d a t a ( A ) \sum data(A) ∑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 m m 条边的无向连通图，求从 s s s 到 t t t 经过 n n n 条边的最短路长度。
1 ≤ n ≤ 1 0 6 1\le n\le 10^6 1≤n≤106， 2 ≤ m ≤ 100 2\le m\le 100 2≤m≤100， 1 ≤ u , v ≤ 1000 1\le u,v\le 1000 1≤u,v≤1000， 1 ≤ w ≤ 1000 1\le w\le 1000 1≤w≤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 n n 多边形，每条边的长度都是 d d d。
从第 1 1 1 个端点开始，每隔 1 1 1 个单位距离就放一个小石头，小石头是白色或者黑色。显然，一条边会有 d + 1 d+1 d+1 个小石头。
现在对放石头有一个规定：最后每条边的白色小石头的数量必须相等。问有多少种不同的方案，答案模 998244353 998244353 998244353。
思路
考虑朴素的 dp，设 f i , 0 / 1 f_{i,0/1} fi,0/1 表示第 i i i 条边尾巴是白/黑的方案数。枚举一条边上有 j ∈ [ 0 , d + 1 ] j\in[0,d+1] j∈[0,d+1] 条白色石头，那么有：
尾巴是白，可以：
(1) 白+白白，中间 d − 1 d-1 d−1 个有 j − 2 j-2 j−2 个白乱排。
(2) 黑+黑白，中间 d − 1 d-1 d−1 个有 j − 1 j-1 j−1 个白乱排。
f i , 0 = f i − 1 , 0 ⋅ C d − 1 j − 2 + f i − 1 , 1 ⋅ C 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} fi,0=fi−1,0⋅Cd−1j−2+fi−1,1⋅Cd−1j−1尾巴是黑，可以：
(1) 白+白黑，中间 d − 1 d-1 d−1 个有 j − 1 j-1 j−1 个白乱排。
(2) 黑+黑黑，中间 d − 1 d-1 d−1 个有 j j j 个白乱排。
f i , 1 = f i − 1 , 0 ⋅ C d − 1 j − 1 + f i − 1 , 0 ⋅ C 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 fi,1=fi−1,0⋅Cd−1j−1+fi−1,0⋅Cd−1j
这就很矩阵啊！直接矩阵快速幂优化：
[ f i , 0 f i , 1 ] = [ f i − 1 , 0 f i − 1 , 1 ] ⋅ [ C d − 1 j − 2 C d − 1 j − 1 C d − 1 j − 1 C d − 1 j ] \begin{bmatrix} f_{i,0} & f_{i,1} \end{bmatrix}=\begin{bmatrix} f_{i-1,0} & f_{i-1,1} \end{bmatrix}\cdot \begin{bmatrix} C_{d-1}^{j-2} & C_{d-1}^{j-1}\\ C_{d-1}^{j-1} & C_{d-1}^j \end{bmatrix} [fi,0fi,1]=[fi−1,0fi−1,1]⋅[Cd−1j−2Cd−1j−1Cd−1j−1Cd−1j]
代码
#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;
}