思路

这个题可以考虑用全部情况减去不合法的情况，来求解。首先需要知道n个点所组成的图总共有\(C(_n^2)\)种，然后用f[n]表示n个点的图联通的方案数。
然后钦定1在联通图里面，考虑不合法的情况。让j个点联通，其他点可以任意连边，这样就可以保证这张图是不连通的。
所以f数组的转移就是
\[f[n]=C(_n^2) - \sum\limits_{i = 1}^{n-1}{f[i] * C(_{n-i}^2)*C(_{n-1}^{i-1})}\]
这是n方的转移，然后可以用**T优化。~~然后我不会~~

O(n^2)代码

#include<cstdio>
#include<iostream>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long ll;
const int N = 5000 + 10,mod = 998244353;
ll C[N][N];
ll read() {
    ll x = 0,f = 1;char c = getchar();
    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;
}
void pre() {
    C[0][0] = 1;
    for(int i = 1;i <= N;++i) {
        C[i][0] = 1;
        for(int j = 1;j <= i;++j) {
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            C[i][j] >= mod ? C[i][j] -= mod : 0;
        }
    }
}
ll f[N];
ll qm(ll x,int y) {
    ll ans = 1;
    for(;y;y >>= 1,x = x * x % mod)
        if(y & 1) ans = ans * x,ans %= mod;
    return ans;
}
int main() {
    int n = read();
    pre();
    f[1] = f[2] = 1;
    for(int i = 3;i <= n;++i) {
        f[i] = qm(2,C[i][2]);
        for(int j = 1;j < i;++j) {
            f[i] = (f[i] - (f[j] * C[i-1][j-1] %mod * qm(2,C[i-j][2]) % mod) + mod) % mod;
        }
    }
    cout<<f[n];
    return 0;
}

正解

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
ld eps=1e-9;
ll pp=998244353;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head
#define N 310000
ll f[N],b1[N],b2[N],inv[N],f2[N],b[N],tt[N],e[N],recf[N],recb[N],Sum[N];
int bel[N];
int n;
ll C(int n,int m){
    if(n<m)return 0;
    if(m==0 || n==m)return 1;
    return b[n]*inv[n-m]%pp*inv[m]%pp;
}
void fnt(ll *a,int n,int fl){
     for(int i=n>>1,j=1;j<n;j++){
       if(i<j)swap(a[i],a[j]);
       int k=n>>1;
       for(;k&i;i^=k,k>>=1);
        i^=k;
     }
     ll g=powmod(3,(pp-1)/n,pp);
     if(fl==-1)g=powmod(g,n-1,pp);
     e[0]=1;
     for(int i=1;i<n;i++)e[i]=mo(e[i-1]*g,pp);
     for(int m=2,t=n>>1;m<=n;m<<=1,t>>=1)
       for(int i=0;i<n;i+=m)
         for(int j=i;j<i+(m>>1);j++){
           ll u=a[j],v=mo(a[j+(m>>1)]*e[(j-i)*t],pp);
           a[j]=u+v;
           if(a[j]>=pp)a[j]-=pp;
           a[j+(m>>1)]=u-v;
           if(a[j+(m>>1)]<0)a[j+(m>>1)]+=pp;
         }
}
void Add(ll &a,ll b){
    a+=b;
    if(a>=pp)a-=pp;
}
int get(){
    return (rand()<<10)+rand();
}
int main(){
    n=read();
    b[0]=inv[0]=1;
    rep(i,1,n)b[i]=b[i-1]*i%pp,inv[i]=powmod(b[i],pp-2,pp);
    
    f[1]=f2[1]=1;
    rep(i,1,n)b1[i]=powmod(2,C(i,2),pp); 
    
    rep(i,1,n)b2[i]=b1[i]*inv[i]%pp;
    int nn=256,n2=nn*2;
    rep(i,1,n)bel[i]=i/nn;
    int num=0;
    ll t=powmod(nn*2,pp-2,pp);
        rep(i,1,n){
        if(i%nn==0){
            rep(j,0,nn*2)tt[j]=0;
            rep(j,1,bel[i]-1){
                int t1=j*n2,t2=(bel[i]-j)*n2;
                rep(k,0,nn*2-1)
                    tt[k]=(tt[k]+recf[t1+k]*recb[t2+k])%pp;
            }
            fnt(tt,nn*2,-1);
            rep(j,0,nn*2-1)Sum[bel[i]*nn+j]=(Sum[bel[i]*nn+j]+tt[j]*t)%pp;
        }
        f[i]=mo(b1[i]-Sum[i]*b[i-1],pp);
        f2[i]=f[i]*inv[i-1]%pp;
        
        for(int j=1;j<i && j<nn;j++)
            Sum[i+j]=(Sum[i+j]+f2[j]*b2[i]+f2[i]*b2[j])%pp;
        if(i<nn)Add(Sum[i+i],f2[i]*b2[i]%pp);
        
        if(i%nn==nn-1){
            rep(j,0,nn*2)tt[j]=0;
            rep(j,bel[i]*nn,i)tt[j%nn]=f2[j];
            fnt(tt,nn*2,1);
            rep(j,0,nn*2-1)recf[bel[i]*n2+j]=tt[j];
            
            rep(j,0,nn*2)tt[j]=0;
            rep(j,bel[i]*nn,i)tt[j%nn]=b2[j];
            fnt(tt,nn*2,1);
            rep(j,0,nn*2-1)recb[bel[i]*n2+j]=tt[j];
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

一言

那是红得像烈焰，像宝石，像盛夏的初恋，比什么都美好的云朵，仿佛天空的一颗心。 ——阿狸·尾巴

[luoguU48834][count]

思路

O(n^2)代码

正解

一言