题解 CF1326F2 Wise Men (Hard Version)

· · 题解

状压神仙题，对于数数神仙可能偏套路但是我不是

主要思路

首先可以想到，最后选择点的顺序在题中给的邻接矩阵上会形成多条链，自然想到压完状态后能不能直接对每条链的方案数进行 dp 呢

答案是不能，因为这样做不能保证两条链能不能合并成一条链（即前面的链的末尾与后面的链的开头有边，这显然不能简单利用乘法原理处理），于是自然想到容斥

设F(x)表示x为最后生成的数的子集的方案数，如果能快速算出所有的F，就可以通过一次高维差分得到真正的结果

注意到此时对于每条链的情况分开计算是合法的，于是开始 dp

\text{Part.1} 预处理

先考虑对于每条链的方案数进行 dp，设长度为|s|的链，且经过|s|集合中的点的方案数为f_s，注意这里一条链正着写一遍点编号是一种方案，倒着写一遍是另一种方案

显然有一个O(2^nn^2)的 dp 可以解决这个问题，设g_{s,u}为链上点集为s，链结尾是u的方案数，a为邻接矩阵，转移为：

g_{s,u}=\sum_{v\in s}g_{s-u,v}a_{u,v} f_s=\sum_{u\in s}g_{s,u}

\text{Part.2} 计算F

接下来我们发现，对于链长度集合完全相同的生成的二进制数，因为只是链交换顺序，所以其方案数是相同的

这告诉我们只需要枚举n的分拆再进行接下来的讨论，oeis 一下就会知道18的整数分拆是385

设\sum\limits_{i=1}^ma_i=n，且：a_1\le a_2\le \dots\le a_m

那么接下来考虑计算F，设h_{i,s}为取到第i条链，已取的集合为s，显然有这样的转移：

h_{i,s}=\sum_{|t|=a_i,t\subseteq s} h_{i-1,s-t}g_t

实际上是一个子集卷积，但是做385遍子集卷积是受不了的（尽管后面会提到这跑不满，但是下面的方法的复杂度仍然比这个方法要优秀），所以再考虑容斥

设h_s为使用一次或多次s集合中的点，链状态形成当前整数分拆的方案数，由于你使用多次使用一个点一定会导致一些点不会被使用，这就是另一种状态，因此这是可以容斥出F的

考虑记录p_{s,j}为从点集s中选取j个点形成链的方案数，由于一个点可以被选多次，所以：

h_s=\prod_{i=1}^mp_{s,a_i}

可以提前使用高维前缀和O(2^nn^2)预处理出p数组，对h的计算是O(2^nm)的，对h进行容斥是O(2^n)，复杂度是O(2^n\sum m)的

然后你大力爆搜一发会发现\sum m=2644，看着一脸不能过这题的样子，请相信 CF 评测机的速度可以让你过这题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define int LL
#define db double
#define INF 2147483647
#define LLINF 9223372036854775807
#define LL long long
using namespace std;
int inline read(){
    int num=0,neg=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')neg=-1;c=getchar();}
    while(isdigit(c)){num=(num<<3)+(num<<1)+c-'0';c=getchar();}
    return num*neg;
}
const int maxn=19,r=998244353,mod=19260817;
LL n,a[maxn][maxn],b,f[maxn][1<<maxn],cnt[1<<maxn];
LL g[1<<maxn],p[maxn][1<<maxn],h[1<<maxn],F[1<<maxn];char str[maxn];
LL c[maxn],sta[maxn];LL res[mod];
void dfs(int x,int sum,int num){
    if(sum==n){
        int P=1,ans=0,s=0;
        for(int i=1;i<=num;i++)ans=(ans+1ll*c[i]*P%mod)%mod,P=1ll*P*r%mod;
        for(int i=1;i<(1<<n);i++){
            h[i]=1;
            for(int j=1;j<=num;j++)
                h[i]=h[i]*p[c[j]][i];
        }
        for(int i=1;i<(1<<n);i++)s+=((n-cnt[i])&1)?-h[i]:h[i];res[ans]=s;return;
    }for(int i=x;i<=n-sum;i++)c[num+1]=i,dfs(i,sum+i,num+1);
}
void FWTor(LL *A,int len,int opt){
    for(int i=1;i<(1<<len);i<<=1)
        for(int j=0;j<(1<<len);j+=(i<<1))
            for(int k=0;k<i;k++)
                A[i+j+k]+=A[j+k]*opt;
}
void FWTand(LL *A,int len,int opt){
    for(int i=1;i<(1<<len);i<<=1)
        for(int j=0;j<(1<<len);j+=(i<<1))
            for(int k=0;k<i;k++)
                A[j+k]+=A[i+j+k]*opt;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++){
        scanf("%s",str+1);
        for(int j=1;j<=n;j++)a[i][j]=str[j]-'0';
    }for(int i=1;i<(1<<n);i++)cnt[i]=cnt[i>>1]+(i&1);
    for(int i=1;i<(1<<n);i++)
        for(int j=1;j<=n;j++)
            if((1<<j-1)&i){
                if(cnt[i]==1){f[j][i]=1;break;}
                for(int k=1;k<=n;k++)
                    if((1<<k-1)&i)
                        f[j][i]+=f[k][i^(1<<j-1)]*a[j][k];
            }
    for(int i=1;i<(1<<n);i++)
        for(int j=1;j<=n;j++)
            g[i]+=f[j][i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<(1<<n);j++)
            if(cnt[j]==i)p[i][j]=g[j];FWTor(p[i],n,1);  
    }dfs(1,0,0);
    for(int i=0;i<(1<<n-1);i++){
        int top=0,tot=-1;
        for(int j=0;j<n-1;j++)
            if((i>>j&1)==0){
                sta[++top]=j-tot;tot=j;
            }sta[++top]=n-tot-1;sort(sta+1,sta+top+1);int P=1,ans=0;
        for(int j=1;j<=top;j++)ans=(ans+1ll*sta[j]*P%mod)%mod,P=1ll*P*r%mod;F[i]=res[ans];
    }n--;FWTand(F,n,-1);for(int i=0;i<(1<<n);i++)printf("%lld ",F[i]);
    return 0;
}