自动搬运

查看原文

来自洛谷，原作者为

	Larunatrecy 举杯邀明月，对影成三人。

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

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

以下是正文

一个暴力。

对于 $S\in [0,n)$，求出旅行的预约值的按位与为 $S$ 的超集的方案数，然后做高维差分就能得到答案。

这样做的好处是，如果我们枚举 $y$，那么所有所有旅行的起点和终点都只需要满足是 $S$ 的超集即可。

设 $f_{i,x}$ 为当前走了 $i$ 步，位于 $x$ 的方案数，转移分为两种：

• 继续当前旅行

$f_{i,x}\times A_{x,y}\to f_{i+1,y}$

• 新开一个旅行

因为旅行至少走一步，所以我们不妨钦定走一步，枚举新旅行的第二个节点。

$[x\& S=S]f_{i,x}\times s_y\to f_{i+1,y}$，其中 $s_y=\sum\limits_{z\&S=S}A_{z,y}$。

同样的理由，初始化也应当钦定走一步。

最后的答案就是 $\sum\limits_{x\&S=x}f_{m,x}$。

把转移写成矩阵 $F$，同时设行向量 $P$ 为 $f$ 的初值，列向量 $Q$ 为求答案的系数数组。

那么恰好经过 $i$ 条边的方案数即为 $PF^{i-1}Q$ ，$i-1$ 是因为初始化先走了一步。

取 $B=\sqrt m$，预处理出 $PF^{k},k\in [0,B)$ 以及 $F^{kB}Q$，因为都是矩阵乘向量，单次复杂度 $O(n^2)$。

总复杂度 $O(n(n^2\sqrt m+n^3\log m+nm))$，能过。

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 64;
const int M = 20005;
int n,m;
inline int myplus(int a,int b){return (a+b>=mod?a+b-mod:a+b);}
struct vec
{
	int mt[N];
	vec(){memset(mt,0,sizeof(mt));}
	int &operator [](int x){return mt[x];}
}Ma[150],Mb[150];
int operator *(vec A,vec B)
{
	int res=0;
	for(int k=0;k<n;k++)
	res=myplus(res,1ll*A[k]*B[k]%mod);
	return res;
}
struct mat
{
	int mt[N][N];
	mat(){memset(mt,0,sizeof(mt));}
	inline int* operator [](int x){return mt[x];}
}G;
mat operator *(mat A,mat B)
{
	mat C;
	for(int k=0;k<n;k++)
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	C[i][j]=myplus(C[i][j],1ll*A[i][k]*B[k][j]%mod);
	return C;
}
vec operator *(vec A,mat B)
{
	vec C;
	for(int i=0;i<n;i++)
	for(int k=0;k<n;k++)
	C[i]=myplus(C[i],1ll*A[k]*B[k][i]%mod);
	return C;
}
vec operator *(mat A,vec B)
{
	vec C;
	for(int i=0;i<n;i++)
	for(int k=0;k<n;k++)
	C[i]=myplus(C[i],1ll*A[i][k]*B[k]%mod);
	return C;
}
mat Pow(mat a,int b)
{
	mat res;
	for(int i=0;i<n;i++)res[i][i]=1;
	while(b)
	{
		if(b&1)res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int A[N][N];
int f[M][N];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	scanf("%d",&A[i][j]);
	int B=sqrt(m)+1;
	int K=log2(n);
	for(int S=0;S<n;S++)
	{
		for(int i=0;i<n;i++)
		{
			int sum=0;
			for(int j=0;j<n;j++)
			{
				G[j][i]=A[j][i];
				if((j|S)==j)sum=myplus(sum,A[j][i]);
			}
			Ma[0][i]=sum;
			Mb[0][i]=((i|S)==i);
			for(int j=0;j<n;j++)
			if((j|S)==j)G[j][i]=myplus(G[j][i],sum);
		}	
		for(int i=1;i<=B;i++)Ma[i]=Ma[i-1]*G;
		G=Pow(G,B);
		for(int i=1;i<=B;i++)Mb[i]=G*Mb[i-1];
		for(int i=0;i<m;i++)f[i+1][S]=Ma[i%B]*Mb[i/B];
	}
	int ans=0;
	for(int E=1;E<=m;E++)
	{
		for(int i=0;i<K;i++)
		for(int j=0;j<n;j++)
		if((j>>i)%2==0)f[E][j]=myplus(f[E][j],mod-f[E][j^(1<<i)]);
		for(int i=0;i<n;i++)ans^=f[E][i];
	}
	cout<<ans;
	return 0;
}