2025.4.9 鮮花

淺談 DAG 計數(shù)

光るなら

雨上がりの虹も
【a me a ga ri no ni ji mo】
【雨過天晴出現(xiàn)的彩虹】
凜と咲いた花も
【rin to sa i ta ha na mo】
【以及凜然綻放的花朵】
色付き溢れ出す
【i ro zu(du) ki a fu re da su】
【都綻放出美麗的色彩】
茜色の空 仰ぐ君に あの日戀に落ちた
【a ka ne i ro no so ra a o gu ki mi ni a no hi ko i ni o chi ta】
【仰望著深紅色的天空的你那天我陷入了對你的迷戀】
瞬間のドラマチック
【shyun kan no do ra ma chi kku】
【如同戲劇性的一瞬間】
フイルムの中の一こまも 消えないよ 心に刻むから
【fu i ru mu no na ka no hi to ko ma mo ki e na i yo ko ko ro ni ki za mu ka ra】
【卻如電影那樣回放著 每個畫面都銘刻在我心里不會消失】
君だよ 君なんだよ
【ki mi da yo ki mi nan da yo】
【是你哦 就是你哦】
教えてくれた
【o shi e te ku re ta】
【告訴了我】
暗闇も光るなら星空になる
【ku ra ya mi mo hi ka ru na ra ho shi zo ra ni na ru】
【在黑暗中發(fā)光的話 就能成為星空】
悲しみを笑顏にもう隠さないで
【ka na shi mi wo e ga o ni mo u ka ku sa na i de】
【悲傷也被笑容掩蓋 已不用再隱藏起來】
煌めくどんな星も君を照らすから
【ki ra me ku don na ho shi mo ki mi wo te ra su ka ra】
【漫天閃耀的繁星都會照亮你前行】
眠りも忘れて迎えた朝日が
【ne mu ri mo wa su re te mu ka e ta a sa hi ga】
【忘記入睡的一夜迎來了晨光】
やたらと突き刺さる
【ya ta ra to tsu ki sa sa ru】
【將我失眠的雙眼刺傷】
低気圧運ぶ 頭痛だって
【te i ki a tsu ha ko bu zu tsu u da tte】
【沉悶與壓抑 令人頭痛心煩】
忘れる 君に會えば
【u su re ru ki mi ni a e ba】
【但若遇見你 就會煙消云散】
靜寂はロマンチック
【se i jya ku wa ro man chi kku】
【寂靜無聲的浪漫氣氛】
紅茶に溶けたシュガーのように
【kou chya ni to ke ta shyu gaa no you ni】
【像溶入紅茶的方糖一樣】
全身に巡るよ 君の聲
【zen shin ni me gu ru yo ki mi no ko e】
【環(huán)繞全身 仿佛聽到了你的聲音】
君だよ 君なんだよ
【ki mi da yo ki mi nan da yo】
【是你哦 就是你哦】
笑顏をくれた
【e ga o wo ku re ta】
【給了我燦爛的笑容】
涙も光るなら 流星になる
【na mi da mo hi ka ru na ra ryuu se i ni na ru】
【淚水若能綻放光芒 流星般閃耀】
傷ついたその手を もう離さないで
【ki zu tsu i ta so no te wo mou ha na sa na i de】
【那受傷過了的手 已經(jīng)不會再次放開】
愿いを込めた空に
【ne ga i wo ko me ta so ra ni】
【在充滿愿望的天空下】
明日が來るから
【a shi ta ga ku ru ka ra】
【明天一定會來到】
導(dǎo)いてくれた光は 君だよ
【mi chi bi i te ku re ta hi ka ri wa ki mi da yo】
【指引引導(dǎo)著我的那道光 是你喲】
つられて仆も走り出した
【tsu ra re te bo ku mo ha shi ri da shi ta】
【我也被帶動著開始邁出了步伐】
知らぬ間にクロスし始めた
【shi ra nu ma ni ku ro su shii ha ji me ta】
【不知和不覺 彼此間開始交匯】
ほら今だ ここで光るなら
【ho ra i ma da ko ko de hi ka ru na ra】
【對就是現(xiàn)在 在這里若能綻放光芒】
君だよ 君なんだよ
【ki mi da yo ki mi nan da yo】
【是你哦 就是你哦】
教えてくれた
【o shi e te ku re ta】
【告訴了我】
暗闇は終わるから
【ku ra ya mi wa o wa ru ka ra】
【懂得黑暗終將逝去】
君だよ 君なんだよ
【ki mi da yo ki mi nan da yo】
【是你哦 就是你哦】
教えてくれた
【o shi e te ku re ta】
【告訴了我】
暗闇も光るなら 星空になる
【ku ra ya mi mo hi ka ru na ra ho shi zo ra ni na ru】
【在黑暗中發(fā)光的話 就能成為星空】
悲しみも笑顏に もう隠さないで
【ka na shi mi mo e ga o ni mou ka ku sa na i de】
【悲傷也被笑容掩蓋 已不用再隱藏起來】
煌めくどんな星も君を照らすから
【ki ra me ku don na ho shi mo ki mi wo te ra su ka ra】
【漫天閃耀的繁星都會照亮你前行】
答えはいつでも偶然必然
【ko ta e wa i tsu de mo guu zen hi tsu zen】
【答案都總是 偶然的必然的】
いつか選んだ道こそ運命になる
【i tsu ka e ran da mi chi ko so un mei ni na ru】
【總有天會知道自己選的道路才是自己該行的命運之路】
握り締めた その希望も不安も
【ni gi ri shi me ta so no ki bou mo fu an mo】
【手中緊握著的那份希望以及不安】
きっと二人を動かす 光になるから
【ki tto fu ta ri wo u go ka su hi ka ri ni na ru ka ra】
【一定會成為照耀兩人前行的光芒】

我不會 EGF，所以不寫和 EGF 有關(guān)的部分。

首先看一道板子：

n 個點的有向完全圖，求刪掉一些邊變成 DAG 的方案數(shù)，\(n \le 5e3\)

考慮每次去掉零度點進行 dp，即設(shè) \(dp_i\) 表示還 \(i\) 個點的方案數(shù)，枚舉去掉的零度點個數(shù)轉(zhuǎn)移。

輕松算重，所以我們施以二項式反演，設(shè)當前轉(zhuǎn)移 \(m\) 個點，設(shè) \(f_m(i)\) 表示恰好 \(i\) 個零度點，\(g_m(x) = \sum\limits_{i = x}^m \dbinom ix f(i)\)，實際意義是至少。

設(shè) \(E(X, Y)\) 表示 \(X\) 向 \(Y\) 連邊的方案數(shù)，因為這是完全圖，設(shè) \(E(|X|, |Y|) = E(X, Y) = |X||Y|\)，有：

\[g_m(x) = \dbinom mx dp_{m - x} 2 ^ {E(x, m - x)} \]

\[f_m(x) = \sum_{i = x} ^ m \dbinom ix (-1) ^ {i - x} g(i) \]

則：

\[\begin{aligned} dp_m &= \sum_{i = 1} ^ m f(i) \\ &= \sum_{i = 1} ^ m \sum_{j = i} ^ m \dbinom ji (-1) ^ {j - i} \dbinom mj dp_{m - j} 2 ^ {E(j, m - j)} \\ &= \sum_{j = 1} ^ m \dbinom mj dp_{m - j} 2 ^ {E(j, m - j)} \sum_{i = 1}^{j} \dbinom ji (-1) ^ {j - i} \\ &= \sum_{j = 1} ^ m \dbinom mj dp_{m - j} 2 ^ {E(j, m - j)} (-(-1) ^ j \dbinom j0 + (1 - 1) ^ j) \\ &= \sum_{j = 1} ^ m \dbinom mj dp_{m - j} 2 ^ {E(j, m - j)} (-1) ^ {j + 1} \end{aligned}\]

于是就是 \(n ^ 2\) 做。

然后看些擴展的：

[ABC306Ex] Balance Scale

轉(zhuǎn)化題面，若沒有 \(=\) 就是給一個無向圖定向求 DAG 數(shù)，直接賀上一個題的式子有：

\[dp_S = \sum\limits_{T\subseteq S, T \not= \varnothing} [E(T, T) = 0] dp_{S / T} (-1) ^ {|T| + 1} \]

考慮到邊不能不選，所以也不存在選邊的系數(shù) \(2^E\)

考慮加上等號，則相當于可以縮點，設(shè) \(sz_S\) 表示 \(S\) 集合內(nèi)連通塊數(shù)，有：

\[dp_S = \sum\limits_{T\subseteq S, T \not= \varnothing} dp_{S / T} (-1) ^ {sz_T + 1} \]

[清華集訓(xùn) 2014] 主旋律

考慮將強連通分量縮完點以后是個 DAG，而只有一個強連通分量不好做，單步容斥。

設(shè) \(dp_S\) 表示集合 \(S\) 刪成一個強連通分量的方案數(shù)，\(f_{S, k}\) 表示將 \(S\) 縮成 \(k\) 個相互獨立的強連通分量的方案數(shù)，有：

\[dp_S = 2 ^ {E(S, S)} - \sum\limits_{T \subseteq S, T \not= \varnothing} dp_{S / T} 2 ^ {E(T, S / T)} \sum\limits_{k = 1 + [T = S]} ^ {|T|} f_{T, k} (-1) ^ {k + 1} \]

\[f_{S, k} = \sum\limits_{T \subseteq S, \min\{S\} \in T} [E(T, S / T) = 0] dp_{T} f_{S / T, k - 1} \]

為了防止算重，我們欽定 \(min\{S\}\) 即 \(S\) 中的最小元一定放在第一個集合中。

其實這樣已經(jīng) \(n3 ^ n\)，不知道題解寫 \(n3 ^ n\) 為啥都要去掉 \(k\)，難道是為了卡常？

考慮優(yōu)化，發(fā)現(xiàn) \(f_{S, k}\) 中的 \(k\) 的意義就是貢獻 \(-1\) 的系數(shù)，不妨設(shè) \(g_S = \sum\limits_{k = 1 + [T = S]} ^ {|T|} f_{T, k} (-1) ^ {k + 1}\)，則：

\[g_S = -\sum_{T \subseteq S, \min\{S\} \in T} [E(T, S / T) = 0] dp_{T} g_{S / T} \]

唯一要注意的就是 \(dp\) 轉(zhuǎn)移時 \(S = T\) 的特判。

預(yù)處理出 \(E(S, S)\)，對于 \(E(T, S / T)\) 單步容斥成 \(E(T, S) - E(T, T)\)，枚舉子集時每次 \(E(T, S)\) 只更新和上次不一樣的地方，均攤下來就不在上限上了。

總復(fù)雜度 \(\mathcal{O}(3 ^ n)\)。

[省選聯(lián)考 2024] 重塑時光

考慮統(tǒng)計方案，也就是統(tǒng)計將 \(\{1, \dots, n\}\) 劃分成 \(k + 1\) 個點集，能使其每個點集都是一個合法的拓撲序，所有點集縮成的大點組成一個 \(DAG\)。

設(shè) \(f_{S, i}\) 表示將 \(S\) 劃分成 \(i\) 個大點的方案數(shù)，\(g_{S, i}\) 表示劃分為 \(i\) 個獨立大點，\(h_{S}\) 表示 \(S\) 合法的拓撲數(shù)。

\[f_{S, i} = \sum_{T \subseteq S} [E(T, S / T) = 0] \sum_{j = 1} ^ i f_{S / T, i - j} g_{T, j} (-1) ^ {j + 1} \]

\[g_{S, i} = \sum_{T \subseteq S, \min\{S\} \in T} [E(T, S / T) = 0, E(S / T, T) = 0] g_{S / T, i - 1} h_T \]

\[h_S = \sum_{s \in S} [E(S / s, s) = 0]h_{S / s} \]

然后就是 \(n^2 3 ^ n\)，據(jù) JJDW 說已經(jīng)能過了。

發(fā)現(xiàn) \(g, h\) 可以 \(n 3 ^ n\)。

將 \(f_{S, i}\) 寫成多項式 \([x^i]F_S\)，\(G_S\) 同理，轉(zhuǎn)移方程：

\[F_S=\sum_{T \subseteq S} [E(T, S / T)] F_{S / T} G_T \]

這是一個卷積，所以 \(F\) 是個 \(n\) 次多項式，我們往里插 \(n + 1\) 個點值即可，單次復(fù)雜度是 \(\mathcal{O}(3 ^ n)\)，總復(fù)雜度 \(\mathcal{O}(n 3 ^ n)\)。

posted @ 2025-04-09 09:58 xrlong 閱讀(149) 評論(9) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

2025.4.9 鮮花

淺談 DAG 計數(shù)

公告

Loading