题解：AT_agc073_a [AGC073A] Chords and Checkered

思路

一块黑色区域一定被奇数条弦包含。

首先，只被一条线包含的区域很好算，一条线会贡献一个答案，乘上个数

2^{n-1}

即为

n \times 2^{n-1}

。

接着，计算被多条弦包含的情况。直接算并不好算，我们令

i,j

两条弦相交，则

i,j

中间的弦必定两两相交。

暴力枚举是会超时的，我们观察

i

和

j

需要满足：

所以可以用双指针求解。最后计算方案，若有

cnt

条弦相交，那么方案为

2^{cnt-1}

，其他弦任选，为

2^{n-cnt-2}

，整理得

2^{n-3} \times cnt

。

两者答案相加即可。