见 此笔记 第6部分。

题目链接：Acwing1828 luogu

题意

$n$ 座城市， $m$ 条道路，任意两个城市之间之多一条道路。
在第 $j$ 天，$i$ 号城市的魔法值为 $f_{i,j}$ 。给出所有的 $f_{i,0}$ ，之后每一个城市的魔法值都是：

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

其中 $\oplus$ 表示异或，$j\ge 1,v_1,…,v_k$ 是所有与 $x$ 直接相连的城市。

给出 $q$ 个询问，每次回答 $a_i$ 天 1 号城市的魔法值。

思路

难度陡增 倍增+矩乘优化DP

看到题目里的 $n\leq 100$ 和这个形式，结合上面两题，你就该想到这个做法（当然还要优化）。

仔细观察，发现最终要求的总是 1 号城市（原题面里的首都）的魔法值。考虑一个 $f_{i,0}$ 如果产生了贡献，首先 1 一定和这个点有一条路径，而且根据异或的性质，异或偶数次跟没异或一样，那么只需要考虑长度为 $a_i$ 的路径个数的奇偶性即可。于是用矩阵快速幂求 $a_i$ 次方即可。

但是还不够——复杂度 $O(n^3qloga)$ ，TLE了！怎么办呢？再想想那个特殊的要求——只需要知道 1 到其他的点的情况，其余都不用考虑。那么可以预处理邻接矩阵的 $2^k$ 次方，倍增即可。复杂度 $O(n^3\log a+qn^2\log a)$

代码

/*
ai的范围是2^32，直接做肯定炸掉。考虑是2的幂次，可以用倍增解决。
首先，用dis[i,j,k]表示i到j长度为2^k的路径数量。矩乘计算dis。 
对于一个询问，把ai二进制拆分。f[i,j]表示前j个二进制里的1，从1到i的方案数。 
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=110,M=35;
ll f[N][M],road[N][N][M],a[N],a1[M];
int n,m,q;

int main()
{
    scanf( "%d%d%d",&n,&m,&q ); 
    for ( int i=1; i<=n; i++ )
        scanf( "%lld",&a[i] );
    for ( int i=1,ta,b; i<=m; i++ )
        scanf( "%d%d",&ta,&b ),road[ta][b][0]=road[b][ta][0]=1;

    for ( int i=1; i<M; i++ )
     for ( int l=1; l<=n; l++ )
      for ( int j=1; j<=n; j++ )
       for ( int k=1; k<=n; k++ )
        road[j][k][i]+=road[j][l][i-1]*road[l][k][i-1];
    for ( int i=1; i<=q; i++ )
    {
        ll tot=0; ll tmp,ans=0; memset( f,0,sizeof(f) );
        scanf( "%lld",&tmp ); 
        for ( int j=M-1; j>=0; j-- )
            if ( (1ll<<j)<=tmp ) a1[++tot]=j,tmp-=1ll<<j;
        f[1][0]=1;
        for ( int j=1; j<=tot; j++ )
         for ( int k=1; k<=n; k++ )
          for ( int l=1; l<=n; l++ )
            f[k][j]+=f[l][j-1]*road[l][k][a1[j]];
        for ( int j=1; j<=n; j++ )
            f[j][tot]&=1;
        for ( int j=1; j<=n; j++ )
            if ( f[j][tot] ) ans^=a[j];

        printf( "%lld\n",ans );
    }
}