ﾚｽ書き込み

ｽﾚへ戻る 写 ﾚｽ栞 ﾚｽ消

---

競技プログラミングにハマるプログラマのスレ 258

PC,ｽﾏﾎ,PHSは ULA べっかんこ 公式(ｽﾏﾎ) 公式(PC) で書き込んでください｡

名前
ﾒｰﾙ
引用切替：ﾚｽｱﾝｶｰのみ
>>262 > あれ、 ?_ が 農に化けた？ > > # 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 可能な素数なので安全に実装できる。
ﾛｰｶﾙﾙｰﾙ SETTING.TXT

---

他の携帯ﾌﾞﾗｳｻﾞのﾚｽ書き込みﾌｫｰﾑはこちら｡書き込み設定で書き込みｻｲﾄの設定ができます｡
・ULA
・べっかんこ(身代わりの術)
・べっかんこ(通常)
・公式(ｽﾏﾎ)
・公式(PC)[PC,ｽﾏﾎ,PHS可]

---

書き込み設定(板別)で板別の名前とﾒｰﾙを設定できます｡

---

ﾒﾓ帳

(0/65535文字)

---

上下板覧索設栞歴

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.010s