每次操作相当于选择相邻的两个字符并删除两个字符中的一个，也就相当于删除中间的字符有两种方案。
枚举剩下的字符是 $A_i$，则删除左边的方案数显然是 $(2(i-1)-1)!!$，删除右边的方案数为 $(2(N-i)-1)!!$，因此总方案数为 ${N-1\choose i-1}(2i-3)!!(2N-2i-1)!!$。对所有 $A_i=1$ 求和即可，时间复杂度 $O(N)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #188 for Problem #3083. Bit Operation
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:00:43
Last updated: 2025-12-13 00:00:47
题解
Comments
No comments yet.