有标号的二分图计数

题目也在COGS上

---

I

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

其中二分图进行了黑白染色，两个二分图不同：边不同 或 点的颜色不同

水题啊，只有黑白之间连边。

\[ \sum_{k=0}^n \binom{n}{k} 2^{k(n-k)} \]

---

II

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

不能简单的除以2，问题在于有的黑白之间不连边

i个连通块，贡献就是\(2^i\)

DP \(f(n,i)\)表示n个点i个连通块的二分图个数，\(O(n^3)\)

考虑生成函数！

\(S(x)\)表示上道题，\(F(x)\)表示本题

还是不好做，因为都与连通块有关，引入\(H(x)\)表示单个连通块！

\[ S(x) = \sum_{i \ge 0} \frac{2^i \cdot H(x)^i}{i!} \\ F(x) = \sum_{i \ge 0} \frac{H(x)^i}{i!} = \sqrt{S(x)}\\ \]

多项式开根即可

---

III

求n个点的二分图(必须连通)的个数。\(n \le 10^5\)

就是\(H(x)\)

就是\(\frac{1}{2} \ln S(x)\)

---

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = 1e5+5, P = 998244353;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;}int n;ll inv[N], fac[N], facInv[N];inline ll C(int n, int m) {return fac[n] * facInv[m] %P * facInv[n-m] %P;}int main() {    freopen("QAQ_bipartite_one.in", "r", stdin);    freopen("QAQ_bipartite_one.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;    }    ll ans = 0;    for(int k=0; k<=n; k++) ans = (ans + C(n, k) * Pow(2, (ll) k * (n-k) % (P-1))) %P;    printf("%lld\n", ans);}
        
       
      
     
    

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N = (1<<18) + 5, P = 998244353, qr2 = 116195171, inv2 = (P+1)/2;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
            
             >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 = (1<<18) + 5, P = 998244353, qr2 = 116195171, inv2 = (P+1)/2;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;}ll inv[N], fac[N], facInv[N];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
            
             0; i--) b[i] = (ll) inv[i] * b[i-1] %P; b[0] = 0; for(int i=l; i