競技プログラミングにハマるプログラマのスレ 258 (311ﾚｽ)

競技プログラミングにハマるプログラマのスレ 258 http://medaka.5ch.net/test/read.cgi/prog/1763044828/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞

---

262: 仕様書無しさん [sage] 2025/11/15(土) 23:00:53.10 あれ、 ?_ が 農に化けた？ # G 二重和を b ごとにまとめ、H[b] = ?_a c_A[a]·C(a, b) を全 b について求める。 C(a, b) = a!/(b!(a-b)!) より、H[b] = inv(b!)·?_{t≥0} (c_A[b+t]·(b+t)!)·inv(t!)。 A’[a] = c_A[a]·a!、F[t] = inv(t!) とおくと、右辺は A’ と F の反転畳み込みで一括計算できる。 A’ を反転して NTT 畳み込み conv を求め、H[b] = inv(b!)·conv[V-b]（V=max(A_i, B_j)）。 最終答えは S = ?_b c_B[b]·H[b]。 前計算 O(V)、畳み込み O(V log V)、合計 O(V log V)。 998244353 は NTT 可能な素数なので安全に実装できる。 http://medaka.5ch.net/test/read.cgi/prog/1763044828/262

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

あと 49 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.005s