A – 两情
这道题人类智慧，我真不知道咋推。
从中间开始向外扩展，然后碰到\(\gcd = 1\)的情况就输出答案即可。
这套题全都是暴力出奇迹系列。
我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。
然后用 sb 线段树搞下就行了，太特么傻逼了。
首先，叶子结点为\(k\)时，整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。
考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点，且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移：
\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]
向新的节点加入统计数据：多了一个叶子结点，要么向左走，加深当前的路径；要么补上最后一个向左走的右节点。
然后就可以写代码了。
刚开始以为是搞\(\log n\)个基底点，然后双向边上面做事情，最后发现找图上最小环的复杂度非常的高。所以 GG。
正解考虑把问题的规模进行缩小：也就是把一些答案预先特判掉。比如说，如果某一个位上有超过三个点连接，那么环的大小就可以被确定为是\(3\)，也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。
再考虑剩下的情况。此时，\(n\)已经缩小了很多，所以我们暴力建图，用 Floyd 跑最小环即可。
这道题是一道好题。
我们可以直接暴力 DP，考虑状态\(dp[i][j]\)为\(i\)个\(1\)与\(j\)个\(-1\)的答案。那么，我们可以从少一个\(1\)的情况和少一个\(-1\)的情况进行转移：
一定要思考，不能想当然。这句话是说给我听的。
把连通块连边，每一次 BFS 扩展就算做一次点击，然后\(O(n^2)\)确定路径长度，再按奇偶性判断就行了。