正解:容斥+$dp$

解题报告:

$umm$虽然题目蛮简练的了但还是有点难理解,,,我再抽象一点儿,就说有$n$个点,点$i$和点$j$之间有$a_{i,j}$条无向边可以连,问有多少种方案可以连成一张联通图

显然考虑容斥呗?设$f_i$表示状态为$i$的点连成联通图的合法方案,$g_i$表示状态为$i$的点随便连边的所有方案

显然$g_i$可以先预处理出来?就等于$\prod_{u,v\in i}a_{u,v}$.然后$f_i$就等于$g_i$减去不合法的数量.不合法数量显然就考虑枚举子集${i}'$,就等于$\sum f_{{i}'}\cdot g_{i-{i}'}$.

但是这样显然依然会有锅,即一个不合法方案会被枚举其包含的联通块次.为了保证不重不漏,就只用枚指定点的联通块大小,比较通常的做法就枚举最大/最小点的联通块大小,也就钦定${i}'$中包含了最大/最小的点

然后就做完了$QwQ$

$over$

因为一些不知名原因我本机$AC$,$BZOJ$上$WA$了(事实上是,$emacs\ AC$,$lemon\ WA$,$darkbzoj\ WA$,$QAQ$

但是我暂时懒得搞了先把代码放上来趴$kk$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define lf double

#define int long long

#define ll long long

#define gc getchar()

#define ri register int

#define rc register char

#define rb register bool

#define lowbit(x) (x&(-x))

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define gdgs(i,x) for(ri i=x-lowbit(x);i;i-=lowbit(i))

const int N=,mod=;

int n,a[N][N],lg[<<N],tot,d[N],cnt;

ll g[<<N],f[<<N],re[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

signed main()

{

    freopen("2560.in","r",stdin);freopen("2560.out","w",stdout);

    n=read();rp(i,,n-)rp(j,,n-)a[i][j]=read();tot=(<<n)-;rp(i,,n-)lg[<<i]=i;g[]=;

    rp(i,,tot)

    {ll tmp=;gdgs(j,i)tmp=1ll*tmp*(a[lg[lowbit(i)]][lg[lowbit(j)]]+)%mod;g[i]=g[i-lowbit(i)]*tmp%mod;}

    rp(i,,tot)

    {

        cnt=;gdgs(j,i)d[cnt++]=lowbit(j);

        rp(j,,(<<cnt)-)re[j]=re[j-lowbit(j)]|d[lg[lowbit(j)]],f[i]=(f[i]+f[i^re[j]]*g[re[j]])%mod;

        f[i]=(g[i]-f[i]+mod)%mod;

    }

    printf("%lld\n",f[tot]);

    return ;

}

巴特西

$bzoj2560$ 串珠子容斥+$dp$

正解:容斥+$dp$

解题报告:

最新文章

热门文章

巴特西

$bzoj2560$ 串珠子 容斥+$dp$

正解:容斥+$dp$

解题报告:

最新文章

热门文章

$bzoj2560$ 串珠子容斥+$dp$