题目描述

H 国的交通由 $n$ 座城市与 $m$ 条道路构成，城市与道路都从 $1$ 开始编号，其中 $1$ 号城市是 H 国的首都。

H 国中一条道路将把两个不同城市直接相连，且任意两个城市间至多有一条道路。

H 国是一个信奉魔法的国家，在第 $j$ 天，$i$ 号城市的魔法值为 $f_{i,j}$。

H 国的魔法师已观测到第 $0$ 天时所有城市的魔法值 $f_{i,0}$ ，且他们还发现，之后的每一天每个城市的魔法值，都将会变为所有与该城市直接相连的城市的前一天魔法值的异或值，即

$f_{x,j}=f_{v_1,j-1}\oplus f_{v_2,j-1}\oplus \cdots\oplus f_{v_k,j-1}$

其中 $j\ge 1$，$v_1,v_2,\cdots,v_k$是所有与 $x$ 号城市直接相连的城市，$\oplus$ 为异或运算。

现在 H 国的国王问了你 $q$ 个问题，对于第 $i$ 个问题你需要回答：第 $a_i$ 天时首都的魔法值是多少。

输入格式

第一行三个用空格分隔的整数 $n,m,q$，表示城市数、道路数与问题数。

第二行 $n$ 个用空格分隔的整数，第 $i$ 个整数表示 $f_{i, 0}$。

接下来 $m$ 行，每行两个用空格分隔的正整数 $u,v$，表示一条连接 $u$ 号城市与 $v$ 号城市的道路。

接下来 $q$ 行每行一个整数，第 $i$ 行的整数表示 $a_i$ 。

输出格式

按顺序输出 $q$ 行，每行一个整数，表示对应问题的答案。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围和约定

对于 $20\%$ 的数据，满足 $a_i \leq 100$。
对于 $40\%$ 的数据，满足 $n \leq 20$。
另有 $30\%$ 的数据，满足 $m=\frac{n(n-1)}{2}$。
对于 $100\%$ 的数据，满足 $1 \leq n,q \leq 1001≤n,q≤100，1 \leq m \leq \frac{n(n-1)}{2}$。

分析

倍增预处理 + 矩阵加速。

认真读一遍题，发现 $n$ 很小，可以使用邻接矩阵存图。

再看一下题目中给出的式子

$f_{x,j}=f_{v_1,j-1}\oplus f_{v_2,j-1}\oplus \cdots\oplus f_{v_k,j-1}$

设$i , j$两点之间连边为 $e_{i , j}$，两点间有边为$1$，否则为$0$，则原式子可以化为

$f_{x , j} = f_{1 , j - 1} \times e_{1 , x} \oplus f_{2 , j - 1} \times e_{2 , x} \oplus \cdots \oplus f_{n , j - 1} \times e_{n , x}$

不难看出，这与矩阵乘法的定义式长的很像，只是把$+$改成了$\oplus$而已。

这样的话，根据矩阵乘法的定义，图中每个城市第$i$天的魔法值就可以通过其$i - 1$天的魔法值与其邻接矩阵进行异或得到。

然后我们就有了一个很无脑的做法：对于每次询问均进行矩阵快速幂，时间复杂度为$O(q \times n^3 \log a)$，可以拿到$40$分的好成绩。

考虑如何优化这个过程，不难看出，我们在进行矩阵快速幂的时候每一次都会乘一次初始邻接矩阵，这个过程是很浪费时间的。

对此，我们进行二进制拆分，倍增预处理出$2^i$天时的初始邻接矩阵，需要时候直接乘上即可。

优化后，预处理时间复杂度为$O(n^3 \log a)$，单次询问为$O(n^2 \log a)$，足以通过本题。

剩下的见代码注释。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define db double
#define ll long long
#define pb push_back
#define MP make_pair
#define ldb long double
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2047483647;
const long long INFL = 9023372036854775807;

int n , m , q;

struct Matrix{
    ll data[105][105] , h , l;
};

Matrix A , B;

Matrix operator * (const Matrix &A , const Matrix &B){
    Matrix C; clean(C.data , 0);

    C.h = A.h , C.l = B.l;
    rep(i , 1 , A.h){
        rep(j , 1 , B.l){
            rep(k , 1 , A.l){
                C.data[i][j] ^= A.data[i][k] * B.data[k][j];
            }
        }
    }
    return C;
}

Matrix twop[50];  //twop[i] 初始邻接矩阵第2^i天时的值
ll f[1001];

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    scanf("%d%d%d" , &n , &m , &q);
    rep(i , 1 , n){
        scanf("%lld" , &f[i]);
    }
    twop[0].h = twop[0].l = n;
    int u , v;
    rep(i , 1 , m){
        scanf("%d%d" , &u , &v);
        twop[0].data[u][v] = twop[0].data[v][u] = 1;    //初始化邻接矩阵
    }
    rep(i , 1 , 31){
        twop[i] = twop[i - 1] * twop[i - 1];
        //预处理第2^i天的邻接矩阵
    }
    ll day;
    while(q --){
        scanf("%lld" , &day);
        Matrix ans;
        rep(i , 1 , n){
            ans.data[1][i] = f[i];
        }
        ans.h = 1 , ans.l = n;
        rep(i , 0 , 31){
            if((day >> i) & 1){ //若这一天需要用上，则直接相乘
                ans = ans * twop[i];
            }
        }
        printf("%lld\n" , ans.data[1][1]);
    }

    return 0;
}