P3890 题解

· · 题解

这个方法来自 @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 组数据卡了这种情况。