CF - 1651E

1651edu后两道的辅导实在是写得稀烂。看起来是撰写人兴冲冲废话了前四分之 三的“导论”，到最后关键的解法已经不耐烦，只略写一小段；细致的部分必须 检查答案代码才能明白。

分辨其解法如下：

  • 引理一，匹配数总和为匹配中顶点数的一半。
  • 引理二，划分中的长度为偶数的环或路径，所有的点都在匹配中。而长为奇的 路径会少一个点。
  • 那么，思路为计算：划分数乘总点数(1)，减不在划分中的点(2)，减在划分中的长度奇 数的路径数(3)。
  • 划分数(1)，即C(n,2)组合数的平方。
  • 不在划分中(2)。对于每个点，即C(n,2)乘，C(i,2)及C(n-i-1,2)的和。i为0至 n-1。
  • 引理三，二分图中，划分中长度奇数的路径，记中心为p。有两端l,r同顶点p 共在划分内；有L,R分别与l,r相连，远离p，且不在划分中。此时在此划分中 此路径符合引理二后一种情况。
  • 那么，中心p对满足包含{l, …, p, …, r}不含L,R的划分贡献负一的点数。 枚举中心p按此计算即得思路中最后的部分(3)。Q.E.D.