题解：P12445 [COTS 2025] 数好图 / Promet

· · 题解

题意：给定 n。求 n 个点的，只能有 i\to j,i<j 边的 DAG 中，恰有 k 个点在任意一条 1\to n 路径上的方案数。

$\color{red} 2\le n\le 10^5.

全文感谢伟大的 le0n 的无私帮助！

有点小麻烦的计数题。注意下面关于点 1,n 可能要有诸多特殊处理，请读者多加小心。

然后 k=0 的答案通过 2^{\binom{n}{2}} 减去 k>0 的答案得出。k=1 的时候答案为 0。不然可能会出问题。

考虑我们对 DAG 上的点分类。对于一个点 x，称其为：

考虑逐步插入点完善这个图。具体的：先求出 F_n 表示大小为 n 的只有一类点的图的方案。再插入若干二类点，然后插入若干三类点。

::::info[一点小解释]

这是因为二类点 完全不影响 一类点的连边方式。

三类点 完全不影响 一、二类点的连边方式。

所以单独考虑一类点图，一二类点图是正确的。

::::

先求 F，考虑一个点是一类点当且仅当其 \text{in},\text{out}\ne 0.

考虑强制 \text{in}\neq 0，然后容斥钦定 j 个 \text{out}=0.

记 f_{i,j} 表示前 i 个，钦定了 j 个 \text{out}=0 的方案数。

初始 f_{1,0}=1，转移就是 f_{i,j}=(f_{i-1,j}+f_{i-1,j-1})\times (2^{i-j-1}-1).

最终 F_{i}=\sum\limits_{j\ge 0} (-1)^j f_{i,j}，注意 F_{1}=0.

然后我们可以 忽略一类之间的连边。

现在考虑什么点 能连向 一二三类点：

发现三类点能连向所有点。

于是假设确定了 p_1,p_2,\cdots p_t 为三类点，则有关三类点的连边的方案数为 2^{\sum n-p_i}.

那我们接下来就考虑 g_{i,j} 表示 i 个点的一二类点图，j 个一类点的方案数。

得出 dp：g'_{1,1}=1,g'_{i,j}=g'_{i-1,j-1}+g'_{i-1,j}(2^{i-1}-1).

由于最后一个点被钦定为一类点，则实际的 g_{i,j}=g'_{i-1,j-1}.

然后三类点同样做个 dp，h_{i,j} 表示前 i 个点，选了 j 个三类点的带 2^{\cdots} 权方案数。

h'_{1,0}=1,h'_{i,j}=h'_{i-1,j}+h'_{i-1,j-1}2^{n-i}

由于 n 一定不是三类点，于是 h_{k}=h'_{n-1,k}，表示 n 个点有 k 个三类点的带权方案数。

然后最后合并一下 F,g,h 即可，就枚举一类点，二类点个数，然后乘一下贡献一下。

\forall i\ge 2,ans_i=F_i\sum\limits_{j=0}^{n-i} g_{n-j,i}h_j=F_i\sum\limits_{j=0}^{n-i} g'_{n-j-1,i-1}h_j

注意代码里的 g,h 代表 dp 中的 g',h'.

::::info[于是你写出了 \mathcal{O}(n^2) 的代码]

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2005;
int n,mod,p2[N],f[N][N],F[N],g[N][N],h[N][N],A[N];
inline int md(int x){return x>=mod?x-mod:x;}
int main()
{
    cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>mod;
    for(int i=*p2=1;i<=n;i++) p2[i]=md(p2[i-1]<<1);f[1][0]=1;
    for(int i=2;i<=n;i++)
    {
        f[i][0]=1ll*f[i-1][0]*(p2[i-1]-1)%mod;
        for(int j=1;j<=i;j++) f[i][j]=1ll*(f[i-1][j]+f[i-1][j-1])*(p2[i-1-j]-1)%mod;
    }
    for(int i=2;i<=n;i++) for(int j=0;j<=i;j++)
        F[i]=md(F[i]+((j&1)?mod-f[i][j]:f[i][j]));

    g[1][1]=1;
    for(int i=2;i<n;i++) for(int j=1;j<=i;j++)
        g[i][j]=(g[i-1][j-1]+1ll*g[i-1][j]*(p2[i-1]-1))%mod;

    h[1][0]=1;
    for(int i=2;i<n;i++) for(int j=*h[i]=1;j<=i;j++)
        h[i][j]=(h[i-1][j]+1ll*h[i-1][j-1]*p2[n-i])%mod;

    for(int i=2;i<=n;i++) for(int j=0;j<=n-i;j++) 
        A[i]=(A[i]+1ll*g[n-j-1][i-1]*h[n-1][j])%mod;

    int s=1;for(int i=1;i<=n*(n-1)/2;i++) s=md(s<<1);
    for(int i=2;i<=n;i++) A[i]=1ll*A[i]*F[i]%mod,s=md(s+mod-A[i]);
    cout<<s<<" ";for(int i=1;i<=n;i++) cout<<A[i]<<" ";
    return 0;
}

::::

根据伟大的 le0n 所说，这个题是能优化的，于是考虑优化。

下面优化可以结合我 n^2 代码理解我优化了什么东西。

先来优化求 F，比较一大坨，不想看可以默认已经算出了。

::::info[求 F]

\\ \, \\ F_{i}=\sum\limits_{j\ge 0} (-1)^j f_{i,j}

把 2^{i-j-1} 的贡献和 j 化归整齐一下，记 p_i=2^{i-1}-1.

考虑先 u_{i,i-j}=f_{i,j}，则 u_{1,1}=1,u_{i,i-j}=(u_{i-1,i-1-j}+u_{i-1,i-j})p_{i-j}.

即 u_{i,j}=(u_{i-1,j-1}+u_{i-1,j})p_{j}.

然后把 u 转置一下，即两维交换，变成 u^T:

&u^T_{1,1}=1,u^T_{i,j}=p_i(u^T_{i-1,j-1}+u^T_{i,j-1}) \\ \\ \Rightarrow\ & u^T_{i,j}=\sum\limits_{1\le k<j} p_{i}^{\,j-k} \cdot u^T_{i-1,k} \\ \Rightarrow\ & u^T_{i}=U_{i}\times u^T_{i-1},U_{i}=\sum\limits_{j\ge 1} (p_ix)^j=\dfrac{p_ix}{1-p_ix} \\ \Rightarrow\ & u^T_i=x\prod\limits_{j=2}^i U_i=x\prod\limits_{j=2}^i \dfrac{p_jx}{1-p_jx} \end{aligned} F_{i}&=\sum\limits_{1\le j\le i} (-1)^j f_{i,j}\\ &=\sum\limits_{1\le j\le i} (-1)^j u^T_{i-j,i}\\ &=(-1)^i[x^i]\sum\limits_{1\le j\le i} (-1)^j u^T_{j}\\ &=(-1)^i[x^i]\sum\limits_{1\le j\le i} (-x) \prod\limits_{k=2}^j \dfrac{-p_kx}{1-p_kx} \end{aligned}

于是可以想象成有若干一次分式 Q_i(x)=\dfrac{c_ix}{a_ix+b_i}，要求 F_i=[x^i]\sum\limits_{j=1}^i\prod\limits_{k=1}^j Q_i(x).

这东西也是可以分治 NTT 做的，不会计算请参考我的文章。

::::

g'_{1,1}=1,g'_{i,j}=g'_{i-1,j-1}+g'_{i-1,j}(2^{i-1}-1) \\ \, \\ \Rightarrow g'_{1}=x,g'_i=(1+(2^{i-1}-1)x)g'_{i-1} \\ \Rightarrow g'_i=x\prod\limits_{k=1}^{i-1} (1+(2^k-1)x) h'_{1,0}=1,h'_{i,j}=h'_{i-1,j}+h'_{i-1,j-1}2^{n-i} \\ \, \\ \Rightarrow h'_{1}=1,h'_i=(1+2^{n-i}x)h_{i-1},h_k=[x^k]h'_{n-1} \\ \Rightarrow h'_{n-1}=\prod\limits_{k=1}^{n-2} (1+2^kx),h_k=[x^k]h'_{n-1} --- 然后我们考虑 $ans_i$ 除 $F_i$ 的部分： $$\begin{aligned} \sum\limits_{j\in [0,n-i]} g'_{n-j-1,i-1}h_j&=[x^{i-1}]\sum\limits_{j\in [0,n-i]}^{n-i} g'_{n-j-1}h_j \\ &=\sum\limits_{j\in [i,n]} g'_{j-1} h_{n-j}\\ &=\sum\limits_{j\in [0,n-1]} g'_{j} h^{R}_{j} \end{aligned}$$ 其中 $h^R_{j-1}=h_{n-j}$，$j$ 的下界能下放到 $0$ 是因为 $g$ 更小项里系数不足 $x^{i-1}$. 于是我们要算多项式 $\sum\limits_{j=0}^{n} g'_{j} h^{R}_{j}$，注意到 $g'$ 是一个前缀连乘形式，于是分治 **NTT** 即可。 理论上能做到 $\mathcal{O}(n\log ^2n)$，但是由于原题模数性质不好，并且太难写了，于是懒得写了。