https://codeforces.com/contest/2268/problem/E
После скучной части про комбинаторику задача сводится к тому, что нужно
20 раз решить такую подзадачу. Есть последовательность a из нулей и единиц длиной 2*10^5. Нужно для каждого shift посчитать сколько существует таких i, что a[i] != a[i + shift].Наверняка это сводится к перемножению каких-то многочленов. Но это же скучно?
На самом деле для каждого
shift нас просят просто взять битсет, сдвинуть его, проксорить, и посчитать количество единиц. Нам,конечно, нужно сделать суммарно 20 * (2*10^5)^2 / 2 = 4*10^11 операций. Но если поделить это число на 64, то получается всего 6 миллиардов, звучит уже не так и страшно. https://codeforces.com/contest/2268/submission/392765224