4921

考虑对每种方案，设其交点数为 \(t\)，我们就给答案加上 \((-1)^t\)。这样算出来的是偶 - 奇的方案数，加上总的方案数再除以二就是答案了。总的方案数可以简单算出，这里略过。 考虑一条边对奇偶性的贡献。发现如果这条边是 \((u,v)\) 其中 \(u<v\)，那么 \([u+1,v-1] ......