伊埃斯的小站
日记

日记

Tue Jun 24 2025
4 分钟
life 日记
743 字

愤怒的元首 Link to

我们设 dpidp_i 表示 ii 个点能组成多少种 DAG。我们发现：一个 DAG 去掉入度为 00 的点一定还是 DAG。我们枚举有 jj 个入度为 00 d 点，有转移：

dpi=∑j=1idpi−j×2j×(i−j)×(ij)dp_i = \sum_{j = 1}^{i}dp_{i - j} \times 2^{j \times (i - j)} \times \binom{i}{j}

这三项分别表示：子图的方案数；总共有 j×(i−j)j \times (i - j) 条备选边，每条边都可以选择取或者不取；ii 里取 jj 个作为入度为 00 的点的方案数。

但是我们发现：这并非恰好 jj 个入度为 00 的点，所以我们需要二项式反演，边转移边反演：

dpi=∑j=1i(−1)j×dpi−j×2j×(i−j)×(ij)dp_i = \sum_{j = 1}^{i}(-1)^j \times dp_{i - j} \times 2^{j \times (i - j)} \times \binom{i}{j}

最终的答案就是 dpndp_n。

Partition Number Link to

讨厌 pdf 英文题面。

我们首先想到一个简单容斥（但我没想到）：

ans=∑i=1n(−1)i×fi,j×gm−jans = \sum_{i = 1}^{n}(-1)^i \times f_{i,j} \times g_{m - j}

其中 fi,jf_{i,j} 表示用 ii 个集合里的数和为 jj 的方案数，gig_i 表示随便乱凑 ii 的方案数。显然，fi,jf_{i,j} 可以 O(nm)O(nm) 预处理，但是这样我们计算答案就变成了 O(n2m)O(n^2m)，显然不行，于是我们把 ∑i=1n(−1)i×fi,j\sum_{i = 1}^{n}(-1)^i \times f_{i,j} 一整个并到 fjf_j 里去，转移就变成了 fj←fj−fj−if_j \gets f_j - f_{j - i}。

现在考虑如何求解 gig_i。有简单的完全背包做法，但是复杂度是 O(m2)O(m^2)，显然过不了。考虑根号分治。对于 i≤mi \le \sqrt{m} 的 gig_i，我我们直接暴力完全背包，复杂度 O(m)O(m)。对于 >m> \sqrt{m} 的，我们设 αi,j\alpha_{i,j} 表示凑出 i×m+ji \times \sqrt{m} + j 的方案数。有转移：αi,j=αi,j−1+αi−1,j−1\alpha_{i,j} = \alpha_{i,j - 1} + \alpha_{i - 1,j - 1}。分别表示：加入一个 11，整体 +1+1，这样就能够凑出所有的方案了。把 αi,j\alpha_{i,j} 加到 gi×m+jg_{i \times \sqrt{m} + j} 上就是了。

数字表格 Link to

设 n≤mn \le m，有：

ans=∏i=1n∏j=1mFgcd⁡(i,j)=∏d=1nFk∑i=1n∑j=1m[gcd⁡(i,j)=k]\begin{aligned} ans & = \prod_{i = 1}^{n}\prod_{j = 1}^{m}F_{\gcd(i,j)} \\ & = \prod_{d = 1}^{n}F_k^{\sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j) = k]} \end{aligned}

指数上那一坨掏出来：

∑i=1n∑j=1m[gcd⁡(i,j)=k]=∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd⁡(i,j)=1]=∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd⁡(i,j)μ(d)=∑d=1n∑i=1⌊nkd⌋∑j=1⌊mkd⌋μ(d)=∑d=1nμ(d)⌊nkd⌋⌊mkd⌋\begin{aligned} & \sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j) = k] \\ & = \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i,j) = 1] \\ & = \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d \mid \gcd(i,j)}\mu(d) \\ & = \sum_{d = 1}^{n}\sum_{i = 1}^{\lfloor \frac{n}{kd} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{kd} \rfloor}\mu(d) \\ & = \sum_{d = 1}^{n}\mu(d)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \end{aligned}

代回原式：

ans=∏k=1nFk∑d=1nμ(d)⌊nkd⌋⌊mkd⌋ans = \prod_{k = 1}^{n}F_k^{\sum_{d = 1}^{n}\mu(d)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor}

枚举 kd=tkd = t：

ans=∏k=1nFk∑d=1nμ(d)⌊nkd⌋⌊mkd⌋=∏t=1n(∏k∣tFkμ(tk))⌊nkd⌋⌊mkd⌋\begin{aligned} ans & = \prod_{k = 1}^{n}F_k^{\sum_{d = 1}^{n}\mu(d)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor} \\ & = \prod_{t = 1}^{n}\left(\prod_{k \mid t} F_k^{\mu(\frac{t}{k})}\right)^{\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor} \end{aligned}

设 fn=∏k∣nFkμ(nk)f_n = \prod_{k \mid n} F_k^{\mu(\frac{n}{k})}，可以 O(nlog⁡n)O(n \log n) 暴力预处理，外层直接数论分块。注意快速幂的复杂度。

后日谈 Link to 后日谈

心情不好不想谈。

也许我练了这么久水平也还是有提升的？


Telegram
Douban
Reddit
Pocket