Codeforces Round #732 (Div. 2) D. AquaMoon and Chess
Codeforces Round #732 (Div. 2) D. AquaMoon and Chess
定义一种分组方法: 对于一串‘01’序列
,若当前位置
,
且
且 当前的
不属于任何一组,那么就将
与
归为一组,例如 '0111011',可以分为两组 分别是 下标 为
和 下表为
通过观察发现不难发现,按照题目要求的变换方法,对于每个状态而言,按照定义的分组方式,他们的组数是永远不变的,而对于未被分组的'1',它在每一种状态下的位置都是不变的,所以题目就转换成 '11' 与 '0' 有多少种本质不同的排列方式,对于这个问题,假设有 个 '11',
个 '0',对于这个问题相当与有
个坑,其中
个坑选 '0',剩下的给'11',那么答案就是