广义矩阵乘法显然满足结合律

· · 题解

前言：事实上，本题想到构造广义矩阵乘法的过程并不容易，而题解几乎都是简单给出最终做法，而并没有思维过程。更重要的，广义矩阵乘法必须要满足结合律，这一点实际上是必须要证明且不可忽略的。感觉本题的精髓并不在向量 trick 上，而是对广义矩阵乘法结合律的证明。

一点小思维，看到异或按位考虑。但是初始可能会想模拟找规律，不过可以发现相当于每一位 \bmod 2 意义下的矩阵乘法。暴力做时间复杂度 O(T(n^3)\log^2)，多次询问可以通过 P4007 和 P6772 的 trick 变成 O(n^3\log ^2+Tn^2\log)，这里后面再说，不过依旧过不了，而 \bmod 2 的操作显然是很浪费的。

这说明不应该按位考虑，套路的，把 32 位 int 状压起来，那么乘 1 就相当于 \And 全集，乘以 0 就是 \And \ 0，此时矩阵乘法为 (xor,and) 矩阵，我们最后会证明它有结合律。

对于多次询问同一 n 较大矩阵的若干次幂，我们可以提前预处理它的 2^k 次方。这部分的复杂度是 O(n^3\log ^2) 的。

每次询问，我们直接对指数二进制拆开，相当于初始矩阵乘以 \log 个转移矩阵，这样貌似仍然是 O(Tn^3\log) 的，但绝大多数情况下初始矩阵都是向量的形式，向量乘以矩阵只需要 O(n^2) 的复杂度。所以总时间复杂度优化至 O(n^3\log ^2+T n^2\log)。

证明 (xor,and) 广义矩阵乘法有结合律：

\begin{aligned} ((AB)C)_{i,j}&=\mathrm{xor} \ (AB)_{i,l}\And C_{l,j} \\ &=\mathrm{xor} \ (\mathrm{xor} \ A_{i,k}\And B_{k,l}) \And C_{l,j} \\ (A(BC))_{i,j}&=\mathrm{xor} \ A_{i,l}\And (BC)_{l,j} \\ &= \mathrm{xor} \ A_{i,l}\And (\mathrm{xor} \ B_{l,k}\And C_{k,j}) \end{aligned}

交换求和下标，即证：

\mathrm{xor} \ (\mathrm{xor} \ A_{i,k}\And B_{k,l}) \And C_{l,j}= \mathrm{xor} \ A_{i,k}\And (\mathrm{xor} \ B_{k,l}\And C_{l,j})

回忆我们如何证明 (+,*) 矩阵的：

\sum_l (\sum_k A_{i,k}\times B_{k,l})\times C_{l,j}=\sum_{l}C_{l,j}\times\sum_k A_{i,k}\times \sum_{k,l} B_{k,l}

而右手边也可以拆成这样的形式，这样做的原因在于乘法对加法有分配率。那么，只需证 \And 对 \mathrm{xor} 有分配率：

(a\ \mathrm {xor} \ b)\And c= (a\And c)\ \mathrm{xor} \ (b\And c)

因此：

\mathrm{xor} \ (\mathop{xor} \ A_{i,k}\And B_{k,l}) \And C_{l,j} = \mathop{\mathrm{xor}} \limits _{l} \ C_{l,j} \And \ \mathop{\mathrm{xor}} \limits _{k} \ A_{i,k}\ \And \ \mathop{\mathrm{xor}} \limits _{k,l} \ B_{k,l}

右手边同理。

upd：实际上，与运算就是 \bmod 2 意义下的乘法， \oplus 就是加法，感性理解的话发现和 (+,*) 矩阵是一样的，所以证明也不是那么必要。

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int read(){
    char c=getchar();int h=0,tag=1;
    while(!isdigit(c)) tag=(c=='-'?-1:1),c=getchar();
    while(isdigit(c)) h=(h<<1)+(h<<3)+(c^48),c=getchar();
    return h*tag;
}
void fil(){
    freopen("P6569_2.in","r",stdin);
    freopen("data.out","w",stdout);
}
const int U=(1ll<<32ll)-1;
struct mat{
    int a[100][100];
    mat () {
        memset(a,0,sizeof a);
    }
    void init() {
        for(int i=0;i<100;i++) a[i][i]=U;
    }
    int * operator [] (int x) {
        return a[x];
    }
    mat operator * (mat b) {
        mat c;
        for(int k=0;k<100;k++) {
            for(int i=0;i<100;i++) {
                for(int j=0;j<100;j++) {
                    c.a[i][j]^=(a[i][k]&b.a[k][j]);
                }
            }
        }
        return c;
    }
}trans,mi[333];
struct vec{
    int a[100];
    vec() {
        memset(a,0,sizeof a);
    }
    vec operator * (mat b) {
        vec c;
        for(int k=0;k<100;k++) {
            for(int j=0;j<100;j++) {
                c.a[j]^=(a[k]&b.a[k][j]);
            }
        }
        return c;
    }
}v0,v;
mat ksm(mat a,int b) {
    if(b==1) return a;
    mat s=ksm(a,b/2);s=s*s;
    if(b%2==1) s=s*a;
    return s;
}
signed main(){
//  fil();
    int n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++) {
        int x=read();
        v0.a[i-1]=x;
    }
    for(int i=1;i<=m;i++) {
        int u=read(),v=read();
        trans[u-1][v-1]=trans[v-1][u-1]=U;
    }
    for(int i=0;i<=31;i++) mi[i]=ksm(trans,1ll<<i);
    for(int i=1;i<=q;i++) {
        int x=read();
        v=v0;
        for(int j=31;j>=0;j--) {
            if(x>=(1ll<<j)) {
                v=v*mi[j];x-=(1ll<<j);  
            }
        }
        cout<<v.a[0]<<"\n";
    }
    return 0;
}