@snuke_
ꑄ꒖ꐇꌅꏂ🐈

Hello 2019 (CodeForces)

細かいことはソースコード見て

C
折れ線を書いて、増加量 X_i と最下点 L_i を求める。
S_i と S_j をくっつけられる条件は、X_i >= 0 かつ X_i = -X_j かつ L_i = 0 かつ L_j = X_j。
L_i < min(X_i,0) のものを弾いて、X_i の値ごとにカウントして後は適当に数える。

D
素因数ごとに独立に計算して後で掛け合わせればいい。
n = p^x をそれぞれ O(Kx) で適当にdp

E
なにこれ

F
mod 2 なので multiset じゃなくて bitset でいい。
「x を追加」と言う操作を bitset[x] ^= 1 じゃなくて for i = xの約数: bitset[i] ^= 1 とすると、
type 2: xor
type 3: and
になって嬉しい。
type 4 は bitset[x] に影響を与えるビットを前計算しとけばいい(参考:メビウス関数)
面白い。

G
(a+b)^k = Σ (k! / i! / (k-i)!) * a^i * b^(k-i)
であることを考えると、a^i / i! みたいなのを持っておけばいいとなるんだけど、O(n*k^2) から落とせない(FFTでlogにしても重いし)

→WA_TLE氏に聞いた ( https://twitter.com/snuke_/status/1081260484513325056 )
・マージ操作をO(min(sz_v,K)*min(sz_u,K))にできれば全体でO(NK)になる
 ・小*小:sz_v*sz_uでマージするのはO(木のサイズ^2)であることを考えると K^2 * N/K = NK
 ・小*大:K*Σ小のサイズ = NK
 ・大*大:高々N/K回しか発生しないため N/K * K^2 = NK

・for i = 0..sz_v: for j = 0..K: X[j] += DP[i]*(i^j)/j! のように計算されるXを考える
・Xを畳み込むと常にO(K^2)になってしまうのでやっぱりDPで畳み込みたい
・よく考えるとXの値が同じになる長さN+1固定のDP'が作れて、sz_vがでかいやつはそっちにすればいい

・DPとXの変換とかをやるとO(K^2)かかったりしてダメだが、超過分をDP[0~K]に足し込んでいくようにすればO(超過分*K)で出来て、Σ超過分 = N-K なのでこれも NK
・O(超過分*K)でやる方法ですが、DP[0~K]へ足しこむ係数をK+1~2KについてまとめてO(K^3)で前計算しておけばいい。
 ・O(K^3)で逆行列を求めて、K回行列積をするのでO(K^3)

追記>
https://codeforces.com/blog/entry/64367
冒頭の式変形を使うと、もっと簡単にdpのサイズをmin(部分木サイズ,K)にできるらしい。行列パートの代わりにスターリング数の前計算だけで良くなって前処理の計算量も手間も減る。


via Twishort Web App

Retweet Reply
Made by @trknov