环状计数问题。
1.破环成链
先不考虑环的限制，计算出合法的链的数目，最后拼起来。
2.动态规划
最初的想法是设 f[k][i][j] 表示前 k 个人放了 i 个男的和 j 个女的，但显然这样没法体现出连续的一段是多少。
可以在最后加一维状态 [0/1]，表示这一位放的是男生还是女生，这样在表示连续这一条件的时候就可以通过人数增加个数和男（女）生增加的个数相同来体现。
我们发现 i+j=k，所以直接优化掉 j 这一维就好了。
转移就是枚举最后一段放了多少个，即枚举向前第一个异性的位置：
f[i][j][1]=k=1∑a−1f[i−k][j−k][0]f[i][j][0]=k=1∑b−1f[i−k][j][1]
可以用前缀和优化做到 O(n2)。
3.统计答案
而题目要求的是环，我们考虑如何从链变成环。
我们可以钦定环的第一个点是男生还是女生，枚举环起始的位置就可以做了。
具体来说，就是把结尾的一段性别相同的段扔到前面去，这样保证能够不重不漏，记这个长度为 i。
我们钦定至少扔一个过去，所以每一中的方案数就是 (i+1)−1=i 个，而剩下的长度就是链了，可以直接使用 f 数组。
假设扔了 i 个女生，那么方案数就是 ∑i=1b−1i×f[n+m−i][n][1]
注意前缀和时女生要从 i−1,j−1 转移，而不是男生。
