自动搬运

查看原文

来自洛谷，原作者为

	Yu_Jie qwq

搬运于2025-08-24 21:53:47，当前版本为作者最后更新于2023-12-22 09:14:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这个方法来自 @realskc。非常感谢 Ta。

首先这个矩阵乘法不满足结合律，不能使用快速幂优化。尝试找一些性质。

因为 $V$ 和 $\bigoplus$ 都是位运算，所以我们可以将二进制下每一位隔离开来。接下来我们只需考虑矩阵中只有 $0$ 和 $1$ 的情况。

把每次矩阵乘法看作 $A^x\times A$ 的形式，因为 $A$ 是不变的，所以我们可以将每行分开考虑。接下来我们要对每行向量 $X$ 求 $X\times A^{m-1}$。

记 $f(X)=X\times A$，表示若 $X$ 的转置与 $A$ 的第 $i$ 列向量完全相同，则 $f(X)_i=0$，否则 $f(X)_i=1$。

接下来给出一个重要结论：对于任意 $X$，至多有 $n+1$ 种不同的 $f(X)$。

对于 $A$ 中的每列向量，将相同的向量归为一类。每类开一个集合，对于第 $i$ 列向量，向其所在类的集合加入 $i$。然后再分别考虑每一类，用一个 $n$ 位二进制数表示它。其中若集合中存在 $i$，则二进制数的第 $i$ 位为 $0$，否则为 $1$。

显然，此时每一类的二进制数表示，加上一个 $n$ 位全 $1$ 的二进制数，就是所有不同的 $f(X)$。

于是 $X$ 在经过至多 $n+2$ 次乘法后就会进入循环。对 $f(X)$ 离散化后可以 $O(1)$ 转移。复杂度 $O(n^2\log v)$。

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,a[N][N],ans[N][N],nxt[2*N],idx,vis[2*N],stk[N],top;
bitset<N> row[N],col[N],all,st[N],buc[2*N];
unordered_map<bitset<N>,int> mp;
int read() {
	int x=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
	return x*f;
}
int main() {
    n=read(); m=read()-1;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++) a[i][j]=read();
    if(!m) {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) printf("%d%c",a[i][j]," \n"[j==n-1]);
        return 0;
    }
    for(int i=0;i<n;i++) all[i]=1;
    for(int k=0;k<30;k++) {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) row[i][j]=col[j][i]=a[i][j]>>k&1;
        mp.clear(); idx=0;
        mp[all]=0; buc[0]=all; st[0]=all;
        for(int i=0;i<n;i++) {
            if(mp.find(col[i])==mp.end())
                mp[col[i]]=++idx,buc[idx]=col[i],st[idx]=all;
            st[mp[col[i]]][i]=0;
        }
        for(int i=0,ii=idx;i<=ii;i++) {
            if(mp.find(st[i])==mp.end())
                mp[st[i]]=++idx,buc[idx]=st[i],nxt[idx]=0;
            nxt[i]=mp[st[i]];
        }
        for(int i=0;i<n;i++) {
            int x=mp.find(row[i])==mp.end()?0:nxt[mp[row[i]]];
            vis[x]=1; stk[++top]=x;
            for(int j=2;j<=m;j++) {
                x=nxt[x];
                if(!vis[x]) {vis[x]=j; stk[++top]=x; continue;}
                x=stk[vis[x]+(m-j)%(j-vis[x])]; break;
            }
            while(top) vis[stk[top--]]=0;
            for(int j=0;j<n;j++) ans[i][j]|=buc[x][j]<<k;
        }
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++) printf("%d%c",ans[i][j]," \n"[j==n-1]);
    return 0;
}

值得一提的是，如果对整个矩阵找循环节而非行向量，进入循环的时间可能非常大。2023.12.20 及以前的所有提交均是错解，第 $9$ 组数据卡了这种情况。