【JZOJ6233】【20190627】心的旋律

清疚 2021-11-17 05:22 107阅读 0赞

## 题目 ##

你需要构造一个\$n\$个点的二分图

定义\$F(A)\$表示左部点集\$A\$能够到达的右部中的点

使得满足 $ F(A) \\lt |A| $ 的集合恰好有 $ k $ 个

\$1 \\le n \\le 32 \\ , \\ 0 \\le k \\le 2^n\$

## 题解 ##

*  当$A = \\emptyset $ 时满足\$F(A) \\lt |A|\$ ，当\$k = 2^n\$时无解
 *  下面都考虑构造满足\$F(A) \\ge |A|\$　的个数为\$k \\ = \\ 2^n - k\$
 *  另\$F\_\{i+1\}\$表示第\$i\$个点的F集合，令$ F\_\{i+1\} \\supset F\_\{i\} $ ，记\$d\_i = |F\_\{i\}|\$，即\$d\_\{i+1\}-d\_i = 0 / 1\$
 *  那么结论是$d\_i $的 \$2^n\$ 个取值恰好一一对应了$ 1 \\to 2 ^ n $ 的 $ k $ 值
    
    并且存在一个更强的结论
    
    ![img][]
 *  证明：  
    考虑如何计算一个\$d\_i\$的方案：  
    \\\[ \\begin\{align\} F&= \\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{d\_i\}(^\{i-1\}\_\{j-1\})\\\\ &= \\sum\_\{i=1\}^\{m\} (^n\_i) - (^\{B\_i - 1\}\_\{\\ \\ \\ i\}) \\\\ \\end\{align\} \\\]  
    记 $ d\_i =1 $ 的位置为 $ B\_ 1  ,  \\cdots  ,  B\_m $ ，只需要证明
    
    (注意组合数的一个竖列和主对角线求和是可化简的)
    
    ＊1.若\$m\_1 \\lt m\_2\$ ，则\$F\_1 \\lt F\_2\$
    
    不妨考虑\$m , m + 1\$ \$m \\lt n\$
    
    $F\_\{m+1\} - F\_\{m\} \\ge (^n \_m) - \[ (^\{n-m\}\_1 )+ (^\{n-m-1\}\_2)+\\cdots+(^\{n-1\}\_m) \] = (^\{n-m-1\}\_0) \\ge 1 $
    
    由于前一半是和\$B\_i\$独立的，所以多加一位的贡献可以覆盖后一半的贡献
    
    ＊2.\$m\_1=m\_2\$，记\$d\_i\$形成的二进制数\$D1 \\gt D2\$ ，则\$F\_1 \\lt F\_2\$
    
    不妨考虑二进制位\$i\$和\$i+1\$的贡献 \$(i \\ge m)\$
    
    \$F\_\{i\} - F\_\{i+1\} \\ge (^i\_m) - \[(^\{i-m\}\_1) +\\cdots + (^\{i-2\}\_\{m-1\}) + (^\{i-1\}\_m) \] = (^\{i-m\}\_0) \\ge 1\$
    
    说明二进制位不同可以覆盖后面所有二进制位的贡献
    
    可以说明上面的所有结论

## Code ##

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=33; typedef pair<ll,ll>pii; int n,d[N];ll K,C[N][N]; pii a[N]; int main(){ freopen("circle.in","r",stdin); freopen("circle.out","w",stdout); scanf("%d%lld",&n,&K); K=(1ll<<n)-K; if(!K)puts("-1"),exit(0); int cnt=0; for(int i=0;i<=n;++i)C[i][0]=1; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)C[i][j]=C[i-1][j-1]+C[i-1][j]; for(cnt=0;C[n][cnt]<K;K-=C[n][cnt++]); for(int i=n,now=0;i&&now<cnt;--i){ if(C[i-1][cnt-now-1]<K)K-=C[i-1][cnt-now-1]; else now++,d[i]=1; } for(int i=1;i<=n;++i)d[i]+=d[i-1]; for(int i=1;i<=n;++i,puts("")) for(int j=1;j<=n;++j)printf(j<=d[i]?"1 ":"0 "); return 0; }

转载于:https://www.cnblogs.com/Paul-Guderian/p/11117943.html

[img]: /images/20211116/d91bde9e56474529bb11c79b836eb480.png