【Codeforces 1107D】Compression

【链接】 我是链接,点我呀:)

【题意】

题意

【题解】

先把所给的压缩形式的字符串转成二进制

然后对获得的01数组做一个前缀和(a[i][j]=以(i,j)为右下角,(1,1)为左上角的矩形内的数字的和)

这样就能O(1)复杂度获得一个长度为x的正方形的区间和了。

这样。我们直接暴力从1..n枚举n的因子x

显然每个因子x要进行(n/x)^2次判断。

有个性质

∑(n/x)^2=n^2*∑(1/(x^2))=n^2*(π^2/6)

所以实际上时间复杂度约等于O(n^2)

【代码】