题目

分析

考虑一个点的权值能被统计到答案当且仅当其到1号点的路径条数为奇数条。

那么设 \(dp[i][x][y]\) 表示从 \(x\) 到 \(y\) 走 \(i\) 步路径条数的奇偶性，

这个可以用矩阵乘法加速，多组询问直接二进制拆分预处理出来即可。

大概就是 \(C[x][y]\) 对所有的 \(A[x][z]*B[z][y]\) 取异或

代码

#include 
#include 
using namespace std;
const int N=100;
typedef unsigned uit;
struct maix{
	bool p[N][N];
}A[32],ANS;
uit a[N]; int n,m,Q;
uit iut(){
	uit ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void print(uit ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
}
maix mul(maix A,maix B,int t){
	maix C;
	for (int i=0;i>j)&1) ANS=mul(ANS,A[j],1);
		for (int j=0;j