##A. zsy家今天的饭 对于 \(\binom{m}{k}\) 种方案，答案是跨过的边权*2-直径。 可以对两部分分别计算贡献。

对于前者，可以考虑计算每条边的贡献。 若将餐厅点集划分为 \(a,b\) 两部分，那么乘上的系数就是 \(\binom{m}{k}-\binom{a}{k}-\binom{b}{k}\)。

对于后者，可以考虑枚举直径的两个端点是谁。 有个结论是，树上到达每个点最远的点，一定在直径的端点上。 所以对于其它点，只要判断与当前枚举端点距离即可。

有个问题是如何处理直径长度相同，通过讨论可以发现只要比较标号就是正确的。   ##B. 划愤 考虑 \(n=2\) 的情况，其实和 \(nim\) 积的式子是一样的。 对于 \(n\) 比较大的情况，也就是把所有的单点 \(sg\) 值积在一起。

发现原问题的构造比较奇怪，其实和行列式有点类似。 然而行列式带了一个 \(-1\) 的系数，然而可以发现异或意义下的 \(-1\) 其实就是不变。 所以只要求行列式就好了。

然而并不会 \(nim\) 积，所以学习了一下。 大概就是解决这样一个问题： \(sg(x,y)=\text{mex}_{i<x\ or\ j<y}(sg(i,j))\)。 然后可以发现这样一些性质： 1.对于 \(y=2^{2^x},z < y\)，有 \(y \otimes z=yz\)。 2.对于 \(y=2^{2^x}\)，有 \(y \otimes y=\frac{3}{2}y\) 3.\(\otimes\) 满***换律、结合律。 4.$0 \otimes x=0,1 \otimes x=x$

这样的话，要求 \(x \otimes y\)，可以先找出最大的 \(p=2^{2^x},p \leq \max\{x,y\}\)。 设 \(x=ap+b,y=cp+d\)，就有 \(x\otimes y=(a \otimes p \oplus b)\otimes (c \otimes p \oplus d)\)，下面用乘法和加法代替 \(nim\) 积和异或。

\[ \begin{aligned} xy&=(ap+b)(cp+d)\\ &=acp^2+bd+bcp+adp\\ &=ac(p+\frac{1}{2}p)+bd+(bc+ad)p\\ &=acp+ac\frac{1}{2}p+bd+((a+b)(c+d)-ac-bd)p\\ \end{aligned} \]

容易发现，这样的做***使四个子问题 \(ac,bd,(a+c)(b+d),ac\frac{1}{2}p\) 规模都达到开根的效果。 这样递归的层数就是 \(\log \log V\)，所以复杂度是 $4^{\log \log V}=(2^{\log \log V})2=\log2V$。 可以预处理 \(x,y<256\)，就跑的很快了。

然后为了能够进行高斯消元，需要处理逆元。 做法大概是，找到任意一个大于 \(y\) 的 $2^{2^x}$，那么 \(y^{-1}=y^{2^{2^x}-2}\)。 大概的理解就是，这个玩意在 \(\bmod 2^{2^x}\) 意义下是封闭的，所以满足费马小定理的样子。

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n;
ull ret[257][257],A[155][155];
inline ull mul(ull x,ull y,int len=32){
	if(x<=1||y<=1) return x*y;
	if(len<=4&&ret[x][y]) return ret[x][y];
	ull a=x>>len,b=x^(a<<len),c=y>>len,d=y^(c<<len),A=mul(a,c,len>>1),B=mul(b,d,len>>1),C=mul(a^b,c^d,len>>1),D=mul(A,1ull<<len-1,len>>1),r=D^B^((C^B)<<len);
	return len<=4?ret[x][y]=r:r;
}
inline ull getinv(ull x,ull y=2,ull r=1){
	while(y&&y<=x) y*=y;
	for(y-=2;y;y>>=1,x=mul(x,x)) if(y&1) r=mul(r,x);
	return r;
}
inline bool gauss(){
	for(int i=1,j;i<=n;++i){
		for(j=i;j<=n&&!A[j][i];++j); if(j>n) return 0;
		swap(A[i],A[j]); ull c=getinv(A[i][i]);
		for(j=i;j<=n;++j) A[i][j]=mul(A[i][j],c);
		for(j=i+1;j<=n;++j) if(A[j][i]) for(int k=n;k>=i;--k) A[j][k]^=mul(A[j][i],A[i][k]);
	}
	return 1;
}
int main(){
	freopen("sui.in","r",stdin);
	freopen("sui.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%llu",&A[i][j]);
	return puts(gauss()?"xiaoDyingle":"xiaoDwandanle"),0;
}

  ##C. 树上的鼠 有个结论是，先手必败与 $1$ 号点在直径的中点等价。

原因大概是这样的，$1$ 号点在中点的话，就可以以 $1$ 号点为根建树出来。 对于先手的每个操作，后手都可以移动到不同子树的相同深度的点，所以先手必败。 如果 $1$ 号点不在中点，那么先手可以直接移动到中点，即先后手互换，所以这个结论是正确的。

所以可以直接用 \(dp\) 来统计这个方案数。 显然只关注子树中每个最大深度的联通块个数，这个玩意一看就很长链剖分。 所以写个长链剖分，对于小于短链长度的部分暴力合并，大于的部分打个后缀乘法标记就行了。