对答案序列求一个高维后缀和，再通过差分将其解出，后者复杂度为$o(n2^{n})$
对于求后缀和后的结果，即01序列仅要求1处有边（不要求0处没有边），那么也即要求将原图划分为若干条长度给定且没有公共点的链
不妨先去枚举链的长度，假设为$\{l_{1},l_{2},...,l_{m}\}$，要求满足$l_{1}\le l_{2}\le ...\le l_{m}$且$\sum_{i=1}^{m}l_{i}=n$，记其对应的方案数为$P(n)$即为A000041，也即有$P(18)=385$
下面，问题即要求出对应的方案数，并加到需要贡献的状态上——
状压dp求出$f_{S}$表示$S$中的点构成链的排列数，时间复杂度为$o(n^{2}2^{n})$
构造$g_{i,S}=\begin{cases}0&(|S|\ne i)\\f_{S}&(|S|=i)\end{cases}$，不难发现方案数即为$(\bigcirc_{i=1}^{m}g_{l_{i}})_{V}$（其中$\circ$为或卷积，$V$为点集），先预处理出$g_{i}$做FWT的结果，再$o(2^{n})$求出乘积在$V$处的值，时间复杂度为$o(n^{2}2^{n}+P(n)2^{n})$
对于其有贡献的状态，即将$\{l_{i}\}$重新排列后不同的序列，注意到每一个状态最多统计一次，因此暴力枚举所有排列（不重复）的复杂度也仅为$o(P(n)2^{n})$
综上，总复杂度为$o(n^{2}2^{n}+P(n)2^{n})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N (1<<18) 4 #define L 19 5 #define ll long long 6 vector<int>v; 7 int n,cnt[N],vis[L]; 8 ll f[N][L],g[L][N],S[N],SS[L][N],ans[N]; 9 char s[L][L]; 10 void FWT(ll *a){ 11 for(int i=0;i<n;i++) 12 for(int j=0;j<(1<<n);j++) 13 if (j&(1<<i))a[j]+=a[j^(1<<i)]; 14 } 15 void get_per(int k,int S,ll s){ 16 if (k==v.size()){ 17 ans[S]+=s; 18 return; 19 } 20 int lst=0; 21 for(int i=0;i<v.size();i++) 22 if ((!vis[i])&&(lst!=v[i])){ 23 vis[i]=1,lst=v[i]; 24 get_per(k+1,((S<<v[i])|((1<<v[i]-1)-1)),s); 25 vis[i]=0; 26 } 27 } 28 void dfs(int k,int lst){ 29 if (!k){ 30 ll s=0; 31 for(int i=0;i<(1<<n);i++) 32 if ((n-cnt[i])&1)s-=S[i]; 33 else s+=S[i]; 34 get_per(0,0,s); 35 return; 36 } 37 memcpy(SS[k],S,sizeof(S)); 38 for(int i=lst;i<=k;i++){ 39 v.push_back(i); 40 for(int j=0;j<(1<<n);j++)S[j]*=g[i][j]; 41 dfs(k-i,i); 42 v.pop_back(); 43 memcpy(S,SS[k],sizeof(S)); 44 } 45 } 46 int main(){ 47 scanf("%d",&n); 48 for(int i=0;i<n;i++)scanf("%s",s[i]); 49 for(int i=0;i<(1<<n);i++)cnt[i]=cnt[i>>1]+(i&1); 50 for(int i=0;i<n;i++)f[1<<i][i]=1; 51 for(int i=1;i<(1<<n);i++) 52 for(int j=0;j<n;j++) 53 if (i&(1<<j)){ 54 g[cnt[i]][i]+=f[i][j]; 55 for(int k=0;k<n;k++) 56 if (((i&(1<<k))==0)&&(s[j][k]==‘1‘))f[i|(1<<k)][k]+=f[i][j]; 57 } 58 for(int i=1;i<=n;i++)FWT(g[i]); 59 for(int i=0;i<(1<<n);i++)S[i]=1; 60 dfs(n,1); 61 n--; 62 for(int i=0;i<n;i++) 63 for(int j=0;j<(1<<n);j++) 64 if (j&(1<<i))ans[j^(1<<i)]-=ans[j]; 65 for(int i=0;i<(1<<n);i++)printf("%lld ",ans[i]); 66 printf("\n"); 67 return 0; 68 }