有标号DAG计数

题目在COGS上

I

求n个点的DAG(可以不连通)的个数。\(n \le 5000\)

2013年王迪的论文很详细了

感觉想法很神，自己怎么想到啊？

首先要注意到DAG中一类特殊的点：入度为0的点。以这些点来分类统计

先是一种\(O(N^3)\)的dp， \(d(i,j)\) i个点j个入度为0，转移枚举去掉j个后入度为0点的个数，乘上连边情况

在弱化条件时特殊化

\(f(n, S)\) n个点，只有S中的点入度为0

\(g(n,S)\) n个点，至少S中的点入度为0

\[ g(n, S) = 2^{\mid s\mid (n-\mid S\mid)} g(n-\mid S\mid, \varnothing) \\ g(n, S) = \sum_{S \subset T} f(n, T)\quad (1) \]

子集反演！

\[ f(n, S) = \sum_{S \subset T} (-1)^{\mid T\mid - \mid S\mid} g(n, S)\quad (2) \]

我们目标是求\(g(n, \varnothing)\),

代入\((1),(2)\)，然后使用枚举集合大小，乘上组合数的技巧，\(m = \mid T\mid, k = \mid S\mid\)。还需要用\(\binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n-m} {k-m}\)替换，最后得到

\[ g(n, \varnothing) = \sum_{k=1}^n (-1)^{k-1} \binom{n}{k} 2^{k(n-k)} g(n-k, \varnothing) \]

完成！

现在尝试直接考虑这个式子的意义：

\[ n个点DAG个数= \ge 1 个入度为0 - \ge 2个入度为0 + \ge 3.... \]

II

求n个点的DAG(可以不连通)的个数。\(n \le 10^5\)

当然要用fft啦！分治或者多项式求逆。

\(2^{k(n-k)}\)怎么办？

和hdu那道题类似，把\((n-k)^2 = n^2 - 2nk + k^2\)代入

但这样会出现\(2^{\frac{n}{2}}\)， 2的逆元\(\mod P-1\)不存在，所以要求2的二次剩余\(x^2 \equiv 2 \pmod {P-1}\)

III & IIII

求n个点的DAG(必须连通)的个数。\(n \le 5000, n \le 10^5\)

和类似的思想...

可以不连通到连通

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = 5005, P = 10007;inline int read() {    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n, g[N];int inv[N], fac[N], facInv[N], mi[P+5];inline int C(int n, int m) {return fac[n] * facInv[m] %P * facInv[n-m] %P;}int main() {    freopen("DAG.in", "r", stdin);    freopen("DAG.out", "w", stdout);    //freopen("in", "r", stdin);    n = read();    inv[1] = fac[0] = facInv[0] = 1;    for(int i=1; i<=n; i++) {        if(i != 1) inv[i] = (P - P/i) * inv[P%i] %P;        fac[i] = fac[i-1] * i %P;        facInv[i] = facInv[i-1] * inv[i] %P;    }    mi[0] = 1;    for(int i=1; i<=P; i++) mi[i] = mi[i-1] * 2 %P;    g[0] = 1;    for(int i=1; i<=n; i++)         for(int k=1; k<=i; k++) g[i] = (g[i] + ((k&1) ? 1 : -1) * C(i, k) %P * mi[k * (i-k) % (P-1)] %P * g[i-k] %P) %P;    printf("%d\n", (g[n] + P) %P);}

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = (1<<18) + 5, P = 998244353, qr2 = 116195171;inline int read() {    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}ll Pow(ll a, int b) {    ll ans = 1;    for(; b; b >>= 1, a = a * a %P)        if(b & 1) ans = ans * a %P;    return ans;}namespace fft {    int rev[N];    void dft(int *a, int n, int flag) {         int k = 0; while((1<
         
          < n) k++; for(int i=0; i
          
           >1]>>1) | ((i&1)<<(k-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int l=2; l<=n; l<<=1) { int m = l>>1; ll wn = Pow(3, flag == 1 ? (P-1)/l : P-1-(P-1)/l); for(int *p = a; p != a+n; p += l) for(int k=0, w=1; k
           
            >1); int n = l<<1; for(int i=0; i

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = 5005, P = 10007;inline int read() {    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n, g[N], f[N];int inv[N], fac[N], facInv[N], mi[P+5];inline int C(int n, int m) {return fac[n] * facInv[m] %P * facInv[n-m] %P;}int main() {    freopen("DAGIII.in", "r", stdin);    freopen("DAGIII.out", "w", stdout);    //freopen("in", "r", stdin);    n = read();    inv[1] = fac[0] = facInv[0] = 1;    for(int i=1; i<=n; i++) {        if(i != 1) inv[i] = (P - P/i) * inv[P%i] %P;        fac[i] = fac[i-1] * i %P;        facInv[i] = facInv[i-1] * inv[i] %P;    }    mi[0] = 1;    for(int i=1; i<=P; i++) mi[i] = mi[i-1] * 2 %P;    g[0] = 1;    for(int i=1; i<=n; i++)         for(int k=1; k<=i; k++)             g[i] = (g[i] + ((k&1) ? 1 : -1) * C(i, k) %P * mi[k * (i-k) % (P-1)] %P * g[i-k] %P) %P;    f[0] = 1;    for(int i=1; i<=n; i++) {        f[i] = g[i];        for(int j=1; j