http://codeforces.com/contest/825/problem/F 解法 文字列の最小周期はKMP法のテーブルを用いて計算できる。kmp[i]は文字列 S の先頭 i 文字を切り出した文字列の prefix と suffix の最大共通部分である。たとえば aabaabaab という文字列ならば 6 である…

http://codeforces.com/contest/825/problem/G 解法 一番最初の黒頂点を根 r として考える。黒頂点に囲まれている部分を black-tree と呼ぶことにする。タイプ1 u-r パスを black-tree に併合すればいい。事前に r-u パス上の最小頂点を求めておくことで O(1…

https://yukicoder.me/problems/no/546 解法 高速メビウス変換というものを紹介する。高速メビウス変換というのは以下のような処理である。 for (int i = 0; i < n; i++) { for (int j = 0; j < 1 << n; j++) { if (~j >> i & 1) { a[j | 1 << i] -= a[j]; }…