自动搬运

查看原文

来自洛谷，原作者为

	allenchoi You are not alone.

搬运于2025-08-24 22:08:02，当前版本为作者最后更新于2023-01-25 22:43:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言：

在写这道题的时候踩了一个大坑，题目要求要在第 $T$ 分钟或以前回到 $1$ 号店，而不是恰好在第 $T$ 分钟。
虽然 yukimianyan 大佬的题解思路写的已经非常清楚了，但我觉得代码有一点看不懂，于是决定用相同的思路再写一篇。

科技：

矩阵乘法、快速幂

思路：

首先不考虑买食材的限制，设 $dp_{x,y}$ 为第 $y$ 秒在 $x$ 号节点的方案数。
则有：
$\begin{cases} dp_{x,0}=[x=1]\\ dp_{x,1}=[(1,x,w)\in E]\\ dp_{x,y}=\sum_{(u,x,w)\in E}dp_{u,y-1}+dp_{u,y-2}(y>1) \end{cases}$
而看到 $N\le25,T\le10^9$ 的范围，就很容易想到矩阵快速幂。
首先一个 $1\times(2n+1)$ 的矩阵 $T_i$ 表示：
$[dp_{1,i-1},dp_{2,i-1}...dp_{n,i-1},dp_{1,i},dp_{2,i}...dp_{n,i},ans]$ 的矩阵。
再设计用于转移的 $(2n+1)\times(2n+1)$ 的矩阵 $base$ （ $T_i=T_{i-1}\times base$ ）。
其中，对于前 $i(i\le n)$ 列，矩阵中 第 $i+n$ 行为 $1$ ，其余均为 $0$ ，用于更新 $dp_{x,i-1}$ 的值（改为原 $dp_{x,i}$ ）。
对于所有的边 $(u,v,w)\in E$ ，应将矩阵中的第 $u+n$ 行，第 $v+n$ 列标为 $1$ (用 $dp_{u,i-1}$ 更新 $dp_{v,i}$ )。
第 $2n+1$ 列的第 $n+1$ 行和第 $2n+1$ 行标为 $1$ ，其余为 $0$ （ $ans$ 加上 $dp_{1,i-1}$ ）。
但是我们发现，转移时并没有利用到 $dp_{u,i-2}$ ，肯定有问题（没有考虑到要买全食材）。
用容斥原理解决这个问题：
设 $F_S$ 表示只能买集合 $S$ 内物品（不能买 $S$ 以外的物品）且最终回到一方案总数，则答案为：
$F_{\begin{Bmatrix}B,J,M,P\end{Bmatrix}}$
$-F_{{\begin{Bmatrix}B,J,M\end{Bmatrix}}}-F_{{\begin{Bmatrix}B,J,P\end{Bmatrix}}}-F_{{\begin{Bmatrix}B,M,P\end{Bmatrix}}}-F_{{\begin{Bmatrix}J,M,P\end{Bmatrix}}}$
$+F_{{\begin{Bmatrix}B,J\end{Bmatrix}}}+F_{{\begin{Bmatrix}B,M\end{Bmatrix}}}+F_{{\begin{Bmatrix}B,P\end{Bmatrix}}}+F_{{\begin{Bmatrix}J,M\end{Bmatrix}}}+F_{{\begin{Bmatrix}J,P\end{Bmatrix}}}+F_{{\begin{Bmatrix}M,P\end{Bmatrix}}}$
$-F_{{\begin{Bmatrix}B\end{Bmatrix}}}-F_{{\begin{Bmatrix}J\end{Bmatrix}}}-F_{{\begin{Bmatrix}M\end{Bmatrix}}}-F_{{\begin{Bmatrix}P\end{Bmatrix}}}$
$+F_\varnothing$
枚举集合 $S$ 。
则此时的 $base$ 矩阵中，对于所有的边 $(u,v,w)\in E\land w\subseteq S$ ，第 $u$ 行第 $v+n$ 列标为 $1$ 。
最后由矩阵乘法的结合律可知：
$F_S=T_1\times {base_S}^T$
时间复杂度 $O(2^k\times \log T \times N^3)$

代码：

//建议定义新矩阵时将其数组无脑memset 防止出错
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 30,M = 510,mod = 5557;
int n,m,T,l,a,b,c,ans,bx[410];
string s;
struct edge{int u,v,w;} g[M];
struct matrix{int n,m,s[N << 1][N << 1];} bgn,base,tmp;
matrix operator *(matrix x,matrix y)
{
	matrix ret;
	ret.n = x.n,ret.m = y.m;
	memset(ret.s,0,sizeof(ret.s));
	for(int i = 1;i <= x.n;i++)
		for(int j = 1;j <= y.m;j++)
			for(int k = 1;k <= x.m;k++)
				ret.s[i][j] = (ret.s[i][j] + x.s[i][k] * y.s[k][j] % mod) % mod;
	return ret;
}
int popcount(int x)
{
	int ret = 0;
	for(int i = 1;i <= 8;i <<= 1) if(x & i) ret++;
	return ret;
}
int v()
{
	int ret = 0;
	l = s.length();
	for(int i = 0;i < l;i++) ret |= bx[s[i]];
	return ret;
}
void init(int s)
{
	memset(base.s,0,sizeof(base.s));
	base.s[n + 1][2 * n + 1] = base.s[2 * n + 1][2 * n + 1] = 1;
	for(int i = 1;i <= n;i++) base.s[i + n][i] = 1;
	for(int i = 1;i <= m;i++)
	{
		base.s[g[i].u + n][g[i].v + n] = 1;
		if((g[i].w & s) == g[i].w) base.s[g[i].u][g[i].v + n] = 1;
	}
}
matrix ksm(matrix x,int y)
{
	matrix ret;
	ret.n = ret.m = 2 * n;
	memset(ret.s,0,sizeof(ret.s));
	for(int i = 1;i <= 2 * n;i++) ret.s[i][i] = 1;
	while(y)
	{
		if(y & 1) ret = ret * x;
		x = x * x;
		y >>= 1;
	}
	return ret;
}
//BJMP
int main()
{
//	freopen("data.in","r",stdin);
	bx['B'] = 1,bx['J'] = 2,bx['M'] = 4,bx['P'] = 8;
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		cin >> a >> b >> s;
		c = v();
		g[i] = (edge){a,b,c};
	}
	cin >> T;
   //bgn就是T1
	memset(bgn.s,0,sizeof(bgn.s));
	bgn.n = 1,bgn.m = base.n = base.m = 2 * n + 1;
	bgn.s[1][1] = 1;
	for(int i = 1;i <= m;i++) if(g[i].u == 1) bgn.s[1][g[i].v + n] = 1;
	for(int i = 15;i >= 0;i--)
	{
		init(i);
		tmp = bgn * ksm(base,T);
		a = tmp.s[1][n * 2 + 1];
		if(popcount(i) & 1) ans = (ans - a + mod) % mod;
		else ans = (ans + a) % mod;
	}
	cout << ans << endl;
	return 0;
}