ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

ARC071E TrBBnsformBBtion 题解

posted on 2021-09-05 15:37:35 | under 题解 |

发现这个操作是可逆的!比如现在有A,变成BB,然后变成AAAA,还可以变回A。唯一的特例是空串,它不能变成任何串,不过这不重要。

既然可逆,那么我们只需要把 $s,t$ 上这两个区间变成一样的,就可以说明它们可以相互转化了。

怎么变?先全变成A,然后看两个区间A的个数模 $3$ 是否相同即可。交上去你发现过了/jy

代码不放了,就是一个前缀和(