「ZJOI2016」小星星题解

_lbw_ · 2023-03-06 18:38:23 · 题解

已有的题解都为较为基础的容斥算法，这种容斥的正确性实际上并不显然。

在此，给出一种基于 \textsf{FWT} 的做法。

设计 f_{i,j,S} 表示 i 的子树里，点 i 对应点为 j，子树值域为 S 的方案数，转移是子集卷积的形式。

对于子集卷积，我们可以使用占位多项式在复杂度多乘一个 n 的代价上转化为异或卷积。

但实际上并不需要占位多项式，考虑直接进行异或卷积的过程。

容易发现我们最后求的是 f_S，而每一个树上的点最多提供一个数，若在异或时存在一位抵消，则最后求出的 |S|<n。

于是我们证明了直接异或卷积的正确性。

接下来将转移写出，便有一个 \mathcal{O}(n^32^n) 的 \textsf{FWT} 做法。笔者对这种做法进行实现再经历数次卡常后发现并不可过。

这种做法似乎已经没有优化空间了，让我们看一下代码：

IV dfs(ll u,ll F){
    for(ll v:g[u])if(v^F)dfs(v,u);
    F(pu,1,n){
        f[u][pu][1<<pu-1]=1;FWT(f[u][pu]);//third line
        for(ll v:g[u])if(v^F){
            mem(tmp,0);
            F(pv,1,n)if(vis[pu][pv])F(j,0,S)tmp[j]+=f[v][pv][j];
            FWT(tmp);F(i,0,S)f[u][pu][i]=f[u][pu][i]*tmp[i];//first line 
        }
        IFWT(f[u][pu]);//second line
    }
}

我们发现 first line 标记处的一次 \textsf{FWT} 可以拆分为对 f_{v,pv} 的 \textsf{FWT} 之和，而 f_{v,pv} 此处的值已经在 second line 处进行了一次 \textsf{IFWT} 。

于是我们想到记录每个点的 \textsf{FWT} 形式，在根处进行一次 \textsf{FWT}。

但我们和还有一个问题没有解决，在 third line 处的一行 \textsf{FWT}。

我们回归 \textsf{FWT} 的定义式，[z^A]\textsf{FWT}(F)=\sum\limits_{B\subseteq S}(-1)^{\textsf{popcount}(A\&B)}[z^B]F，而此处 F 只有一个位置有值，暴力即可。

我们在一系列的优化后，尽管复杂度不变，但具有更加优美的形式，且不需要用到 \textsf{FWT}。

因此常数有显著的下降，笔者实现后发现可以通过此题。

const int maxn = 20;
const int maxS = (1<<17);
ll n,S,f[maxn][maxn][maxS];bool vis[maxn][maxn];
vector<ll>g[maxn];IV add(ll u,ll v){g[u].push_back(v);}
ll tmp[maxS];IV print(ll S){F(i,0,n-1)putchar((S>>i&1)+'0');}ll tot;
IV dfs(ll u,ll F){
    for(ll v:g[u])if(v^F)dfs(v,u);
    F(pu,1,n){
        F(k,0,S)f[u][pu][k]=(__builtin_popcount((1<<pu-1)&k)&1)?-1:1;
        for(ll v:g[u])if(v^F){
            mem(tmp,0);
            F(pv,1,n)if(vis[pu][pv])F(j,0,S)tmp[j]+=f[v][pv][j];
            F(i,0,S)f[u][pu][i]=f[u][pu][i]*tmp[i];
        }
    }
}
int main(){
    n=read();S=(1<<n)-1;ll m=read();
    while(m--){ll x=read(),y=read();vis[x][y]=vis[y][x]=1;}
    F(i,1,n-1){ll x=read(),y=read();add(x,y);add(y,x);}dfs(1,0);ll ans=0;
    F(i,1,n){ll tmp=0;F(j,0,S)tmp+=f[1][i][j]*((__builtin_popcount(S&j)&1)?-1:1);ans+=tmp/(S+1);}
    return cout<<ans,0;
}

闲话：这里的 FWT 可能实际上严谨的证明了容斥的正确性？

「ZJOI2016」小星星 题解

「ZJOI2016」小星星题解