Readme

2489.Number-of-Substrings-With-Fixed-Ratio

对于区间，我们固定会联想到前缀和的应用。在本题里，如果一个区间[a,b]里的0/1比是固定的num1:num2，那么对于前缀prefix[b]和prefix[a-1]应该有什么共同的性质呢？

此前我们遇到过类似的题目：如果区间[a,b]的元素和能被k整除，那么必然prefix[b]和prefix[a-1]关于k的余数一定相同。

类似的，本题里，我们希望prefix[b]和prefix[a-1]应该是关于“num1个0 + num2个1"这个“循环节”的余数相同。怎么定义这个余数呢？假设前缀长度L里面有a个0与b个1，我们可以知道里面出现了k次“num1个0 + num2个1"，其中k=min(a/num1,b/num2)。去除这些完整的循环节，剩下的零头的0与，就代表了“余数”。

所以我们定义hash表，key是“整除循环节后两种字符的零头”，value就是这个前缀出现了多少次。我们依次处理前缀，当该前缀的零头是{a,b}，我们就看hash表里这样的零头pair已经出现过了多少次（前缀），这就意味着可以组成多少对区间，使得该区间里两种字符的个数恰好是“num1个0 + num2个1"的整数倍。