自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:24:30，当前版本为作者最后更新于2022-03-21 19:25:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

有趣的题目 . 建议评分 : 紫 .

考虑把每个字母看做一个点 , 距离看做边 , 那么就相当于在有向图上找长度不超过 $N$ 的路径 .

好像比较难 , 先来看几个简单问题 .

问题 1

给你一个图 , 节点数 $n \le 100$ , 求任意两点间经过 $m(m \le 10^{18})$ 条边的方案数 .

我会 DP ! $dp_{i,j,k}$ 表示从 $i$ 到 $j$ 经过 $k$ 条边的方案数 . 转移方程 : $dp_{i,j,k}=\sum dp_{i,v,k-1} , (v,j) \in E$ .

根据经验 , 如果一个 DP 朴素写法只改变一个维度 , 这个维度只与上一个有关系 , 那么可以矩阵加速 .

尝试构造转移矩阵 , 把第 $k$ 条边的情况向第 $k+1$ 条转移 , 发现这个矩阵就是图的邻接矩阵 !

初始矩阵应为单位矩阵 ($dp_{i,i,0}=1$) , 所以答案矩阵就是邻接矩阵的 $m$ 次幂 ! 矩阵快速幂解决 .

问题 2

给你一个图 , 节点数 $n \le 50$ , 每条边的边权不超过 $5$ , 求任意两点间经过权值和为 $m(m \le 10^{18})$ 的边互相到达的方案数 .

和上一个问题很相似 , 可惜上一个算法不再使用 . 考虑拆点 , 给每一个点 $4$ 个附属点 . 这 $5$ 个点排成一条链 .

如果 $u$ 到$v$ 的边权为 $k$ , 那么就在 $u$ 的第 $k$ 个点向 $v$ 连边 . 这样从 $u$ 到 $v$ 就经过 $k$ 条边 . 这时就和上一个问题一样了 .

然后回归本题 . 用问题 2 中的算法可以解决长度为 $N$ 的路径数 . 那么长度小于 $N$ 怎么办呢 ? 想办法补一些点让它变成 $N$ ! 那么避免重复 , 就加在最前面 .

我们可以创建一个虚点 , 向自己和其它字母的主点连边 , 这样找从虚点到主点长度为 $N+1$ 的路径 , 就一定是在虚点停留若干长度后 , 从一个点到另一个点 . 这样就可以找到长度小于 $N$ 的路径了 !

练习题 :

P4159 [SCOI2009] 迷路

P2886 [USACO07NOV] Cow Relays G

P3758 [TJOI2017] 可乐

code :

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=200+10,MOD=1e9+7;
struct Matrix {
	int n,m,val[MAXN][MAXN];
	void init(int N,int M) {
		return n=N,m=M,memset(val,0,sizeof(val)),void();
	}
	void output(void) {
		printf("Matrix Output:\n%lld %lld\n",n,m);
		ffor(i,1,n) {
			ffor(j,1,m) printf("%lld ",val[i][j]);
			printf("\n");
		}
		return ;
	}
};
Matrix unit_matrix(int n) {
	Matrix res;
	res.init(n,n);
	ffor(i,1,n) res.val[i][i]=1;
	return res;
}
Matrix operator *(Matrix A,Matrix B) {
	Matrix res;
	int p=A.n,q=A.m,r=B.m;
	res.init(p,r);
	ffor(k,1,q) ffor(i,1,p) ffor(j,1,r) res.val[i][j]+=A.val[i][k]*B.val[k][j],res.val[i][j]%=MOD;
	return res;
} 
Matrix operator ^(Matrix A,int p) {
	Matrix base=A,res=unit_matrix(A.n);
	while(p) {
		if(p&1) res=res*base;
		base=base*base,p>>=1;
	}
	return res;
}
int n,m;
signed main() {
	Matrix A;
	A.init(5*26+1,5*26+1);
	cin>>n>>m;
    ffor(i,1,26) A.val[i][i+26]=A.val[i+26][i+26*2]=A.val[i+26*2][i+26*3]=A.val[i+26*3][i+26*4]=1;
	ffor(i,1,26) ffor(j,1,26) A.val[i][j]=A.val[j][i]=1;
	ffor(i,1,m) {
		char ch1,ch2;int len;
		cin>>ch1>>ch2>>len;
		A.val[ch1-'a'+1][ch2-'a'+1]=A.val[ch2-'a'+1][ch1-'a'+1]=0;
		A.val[ch1-'a'+1+26*(len-1)][ch2-'a'+1]=1,A.val[ch2-'a'+1+26*(len-1)][ch1-'a'+1]=1;
	}
	ffor(i,1,26) A.val[131][i]=1;
	A.val[131][131]=1,A=A^(n+1);
	int ans=0;
	ffor(i,1,26) ans+=A.val[131][i],ans%=MOD;
	cout<<ans;
	return 0;
}