一些题目

[NOI Online #3 提高组] 魔法值

题面：https://www.luogu.com.cn/problem/P6569

题解：将每个f[i][0]分开看，就变成了每个f[i][0]从i点开始随机游走，如果到底根节点的路径有奇数条，就会有贡献，可以通过将邻接矩阵次方来算出奇偶，可以通过预处理\(2^k\)矩阵优化，由于只关心奇偶，可以用bitset优化。

邻接矩阵的n次幂意义:设A（n x n）为一个图的邻接矩阵，则a(i,j)表示两个点之间是否连通（1：连通，0：不连通）。那么A的k次方中的每一个a（i，j）表示点i和j之间长度为k的路的条数。假设一个图能划分成若干个子图，每个子图之间不相连，那么\(A^1 +A^2+…+A^n\)能表示该图的连通性。为0则不可能在一个子图，为非0则可以在一个子图。(摘自：https://blog.csdn.net/snake_seeker/article/details/115377397)