【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)

【代碼】