1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
| #include <bits/stdc++.h> using namespace std; #define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout) #define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++) #define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--) #define DEBUG(x) cout<<#x<<"="<<x<<endl; #define all(x) (x).begin(),(x).end() #define cle(x) memset(x,0,sizeof(x)) #define lowbit(x) ((x)&-(x)) #define ll long long #define ull unsigned ll #define db double #define lb long db #define pb push_back #define mp make_pair #define fi first #define se second const int N=20; const int M=(1<<19)+5; int n,cnt,cnt2; bool bo[N][N]; ll dp[M][N]; int num[M]; ll f[N][M],g[N][M],ans[M]; inline void fwt(ll *a,int n) { for(int i=1;i<n;i<<=1) for(int j=0;j<n;j+=(i<<1)) for(int k=0;k<i;k++) a[i+j+k]+=a[j+k]; } inline void init() { fo(i,1,cnt-1) num[i]=num[i-lowbit(i)]+1; fo(i,0,n-1) dp[1<<i][i]=1; fo(i,1,cnt-1) fo(j,0,n-1) if((1<<j)&i) fo(k,0,n-1) if((1<<k)&i) if(k!=j&&bo[k][j]) dp[i][j]+=dp[i^(1<<j)][k]; fo(i,0,cnt-1) fo(j,0,n-1) if((1<<j)&i) g[num[i]][i]+=dp[i][j]; fo(i,1,n) fwt(g[i],cnt+1); f[0][0]=1; fwt(f[0],cnt+1); } int b[N],a[N],tot; bool used[N]; vector<int> v; void find(int k) { if(k>tot) { int s=0,now=0; fo(i,1,tot) { fo(j,0,b[i]-2) s|=(1<<now),now++; now++; } v.pb(s); return; } fo(i,1,tot) if(!used[i]) if(!(i&&a[i]==a[i-1]&&!used[i-1])) { used[i]=1; b[k]=a[i]; find(k+1); b[k]=0; used[i]=0; } } inline void solve(int m) { tot=m; v.clear(); find(1);
ll sum=0; fo(i,0,cnt-1) sum+=f[m][i]*(((n-num[i])&1)?(-1):1); for(auto u:v) ans[u]=sum; } void dfs(int res,int top,int m) { if(!res)return solve(top-1); fo(i,m,res) { Sum++; a[top]=i; fo(j,0,cnt-1) f[top][j]=f[top-1][j]*g[i][j]; dfs(res-i,top+1,i); } a[top]=0; } int main() { scanf("%d",&n); cnt=(1<<n); cnt2=1<<(n-1); char ss[20]; fo(i,0,n-1) { fo(j,0,n-1) bo[i][j]=ss[j]=='1'; } init(); dfs(n,1,1); DEBUG(Sum); fo(i,0,n-2) fo(j,0,cnt2-1) if(!(j>>i&1)) ans[j]-=ans[j^(1<<i)]; fo(i,0,cnt2-1) printf("%lld ",ans[i]); return 0; }
|