[洛谷P4841]城市规划

我真的菜，这道题从冬令营day0开始想起想到现在才想出来，然后发现真的是一道多项式求逆板子题。我已经菜出一种境界了。

下面分享一下我做这道题的经历（欢迎大家来嘲讽我）：

首先看到这道题我就想了一个神奇的$O(n^3)$的DP，貌似和$n!$暴力一样只能拿20分，感觉特别不爽。这个做法是这样的：

考虑我们做Dinic的时候一开始对一个图分的层（可能是我网络流做多了脑子做傻了），然后可以发现一张任意的无向简单连通图都可以以1为源点唯一地表示为一个分层的模式。所以我们DP一下这个分层的模式就可以了。我们发现转移下一层的代价只与上一层的个数有关，所以我们定义状态：$f(i,j)$表示i个节点，分层之后最后一层有j个的简单无向联通图的个数。然后这个一个$2d/1d$动态规划，我不知道怎么优化。我一直觉得这个想法很精妙，所以一直陷在这个深坑里跳不出来。这非常好地说明了我是傻逼。

我感觉正解状态应该是一维的，但是我之前的想法怎么也优化不到一维。最终我恼羞成怒，强行把它搞到一维。那状态是什么呢？肯定是$f(i)$表示i个点的无向简单联通图的个数了。那么我考虑转移，考虑第i个点是不是割点，如果是割点，那么枚举割掉i之后1所在联通块大小，然后随便转移一下就可以了，但是不是割点怎么办啊？我怎么知道啊。

所以我又鸽了，我好菜了。我突然发现貌似可以把所有简单无向图的个数算出来，然后减去不联通的个数。怎么减呢？枚举1所在联通块有多少个点就可以了。于是我非常开心地写出了一个$1d/1d$动态规划：

$f(i)=2^{C_i^2}-\displaystyle\sum_{j=1}^{i-1}C_{i-1}^{j-1}f(j)2^{C_{i-j}^2}$

那么我们把它拆开来：

$f(i)=2^{C_i^2}-(i-1)!\displaystyle\sum_{j=1}^{i-1}\frac{f(j)}{(j-1)!}\times\frac{2^{C_{i-j}^2}}{(i-j)!}$

感觉这个$(i-1)!$特别烦，那么我们把它除掉：

$\frac{f(i)}{(i-1)!}=\frac{2^{C_i^2}}{(i-1)!}-\displaystyle\sum_{j=1}^{i-1}\frac{f(j)}{(j-1)!}\times\frac{2^{C_{i-j}^2}}{(i-j)!}$

设$A(x)=\frac{f(x)}{(x-1)!}$，$B(x)=\frac{2^{C_x^2}}{(x-1)!}$，$C(x)=\frac{2^{C_x^2}}{x!}$

那么原式子相当于：

$A(x)=B(x)-A(x)C(x)$

变形一下：

$A(x)=\frac{B(x)}{C(x)+1}$

B和C我们都是知道的，那么按照这个式子算一下A，然后用A就可以求出$f(n)$了。

代码：

\#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1<<18|5,MOD=1004535809;
typedef long long ll;
int inv[MAX_N],fac[MAX_N],fac_inv[MAX_N];
inline int fpow(int x,ll n){
    int ret=1;
    for(;n;n>>=1,x=(ll)x*x%MOD)
        n&1?ret=(ll)ret*x%MOD:0;
    return ret;
}
namespace POLY{
    int w[MAX_N],inv[MAX_N];
    void init(){
        for(int i=0;i<=18;++i) w[1<<i]=fpow(3,(MOD-1)/(1<<i));
        for(int i=0;i<=18;++i) inv[1<<i]=fpow(1<<i,MOD-2);
    }
    inline void NTT(int a[],int n,int t){
        if(t==-1) reverse(a+1,a+n);
        for(int i=0,pos=0;i<n;++i){
            if(i<pos) swap(a[i],a[pos]);
            for(int p=n>>1;(pos^=p)<p;p>>=1);
        }
        static int p[MAX_N]; p[0]=1;
        for(int step=1;step<n;step<<=1){
            int stepx=step<<1,wn=w[stepx];
            for(int i=1;i<step;++i) p[i]=(ll)p[i-1]*wn%MOD;
            for(int i=0;i<n;i+=stepx)
                for(int j=i;j<i+step;++j){
                    int x=a[j],y=(ll)a[j+step]*p[j-i]%MOD;
                    a[j]=x+y>=MOD?x+y-MOD:x+y;
                    a[j+step]=x-y<0?x-y+MOD:x-y;
                }
        }
        if(t==-1) for(int i=0;i<n;++i) a[i]=(ll)a[i]*inv[n]%MOD;
    }
    void get_inv(int a[],int b[],int n){
        static int g[MAX_N];
        b[0]=fpow(a[0],MOD-2);
        for(int sz=2;sz<=n;sz<<=1){
            for(int i=sz>>1;i<sz+sz;++i) b[i]=g[i]=0;
            for(int i=0;i<sz;++i) g[i]=a[i];
            NTT(b,sz+sz,1); NTT(g,sz+sz,1);
            for(int i=0;i<sz+sz;++i)
                b[i]=(ll)b[i]*(2ll+MOD-(ll)b[i]*g[i]%MOD)%MOD;
            NTT(b,sz+sz,-1);
        }
    }
    void times(int a[],int b[],int n){
        NTT(a,n,1); NTT(b,n,1);
        for(int i=0;i<n;++i) a[i]=(ll)a[i]*b[i]%MOD;
        NTT(a,n,-1);
    }
}
void fac_init(int n){
    fac[0]=inv[0]=inv[1]=fac_inv[0]=1;
    for(int i=1;i<=n;++i){
        fac[i]=(ll)fac[i-1]*i%MOD;
        if(i>1) inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
        fac_inv[i]=(ll)fac_inv[i-1]*inv[i]%MOD;
    }
}
int a[MAX_N],b[MAX_N],c[MAX_N],p[MAX_N];
int main(){
    POLY::init();
    int n,top; scanf("%d",&n);
    fac_init(n);
    for(top=1;top<=n+1;top<<=1);
    for(int i=1;i<=n;++i) p[i]=fpow(2,(ll)i*(i-1)/2);
    for(int i=1;i<=n;++i){
        b[i]=(ll)p[i]*fac_inv[i-1]%MOD;
        c[i]=(ll)p[i]*fac_inv[i]%MOD;
    }
    c[0]=(c[0]+1)%MOD;  
    POLY::get_inv(c,a,top);
    POLY::times(a,b,top+top);
    printf("%lld",(ll)a[n]*fac[n-1]%MOD);
    return 0;
}