NOI.AC #31. MST

好像又是神仙dp。。。。gan了一早上

首先这是个计数类问题，上DP，

对于一个最小生成树，按照kruskal是一个个联通块，枚举边小到大合成的

假如当前边是树边，那么转移应该还是枚举两个块然后合并

假如不是树边那么就在所有联通块所有非树边中任选一条

两个相邻树边之间的非树边方案应该是P（所有联通块总边数-（当前枚举到那条边-1），r-l-1）

然而按照我现在的智商还是不会捉

%了题解发现一个非常强大的性质，就是对于一个整数的无序拆分很小，40只有37338

设f[zt]，其中zt表示一个状态，由一些联通块的大小组成，总和为n

这样可以爆搜一波把所有无序拆分也就是状态弄出来，并给一个新编号

转移就是枚举两个联通块然后合并

若第i,j个合并

(新状态的方案)+=(这个状态的方案)*(两条树边之间其他边选择的方案)*(第i个联通块的大小)*(第j个联通块的大小)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<map>

using namespace std;

typedef long long LL;

const LL mod=1e9+;

int n;

struct zhuangtai

{

    int u[];

    friend bool operator >(zhuangtai z1,zhuangtai z2)

    {

        if(z1.u[]==z2.u[])

        {

            for(int i=;i<=z1.u[];i++)

                if(z1.u[i]!=z2.u[i])return z1.u[i]>z2.u[i];

        }

        return z1.u[]>z2.u[];

    }

    friend bool operator <(zhuangtai z1,zhuangtai z2)

    {

        if(z1.u[]==z2.u[])

        {

            for(int i=;i<=z1.u[];i++)

                if(z1.u[i]!=z2.u[i])return z1.u[i]<z2.u[i];

        }

        return z1.u[]<z2.u[];

    }

    int getsum()

    {

        int ret=;

        for(int i=;i<=u[];i++)

            ret=(ret+(u[i]*(u[i]-)/)%mod)%mod;

        return ret;

    }

}mp[];int z,g[];

bool cmp(zhuangtai z1,zhuangtai z2){return z1>z2;}

map<zhuangtai,int>id;//通过状态找编号

void dfs(int d,int last)//预处理拆分n的方案

{

    if(d==n)

    {

        z++;

        for(int i=;i<=g[];i++)mp[z].u[i]=g[i];

        return ;

    }

    for(int i=last;i+d<=n;i++)

    {

        g[++g[]]=i;

        dfs(i+d,i);

        g[g[]--]=;

    }

}

LL quick_pow(LL A,LL p)

{

    LL ret=;

    while(p!=)

    {

        if(p%==)ret=ret*A%mod;

        A=A*A%mod;p/=;

    }

    return ret;

}

LL fac[],fac_inv[];

LL getP(int n,int m){return fac[n]*fac_inv[n-m]%mod;}

zhuangtai t;int h[];

int getnzt(int zt,int x,int y)

{

    memcpy(h,mp[zt].u,sizeof(h));

    int d=h[x]+h[y]; memset(t.u,,sizeof(t.u));

    for(int i=;i<=h[];i++)

    {

        if(i!=x&&i!=y)

        {

            if(d!=-&&h[i]>d)t.u[++t.u[]]=d,d=-;

            t.u[++t.u[]]=h[i];

        }

    }

    if(d!=-)t.u[++t.u[]]=d;

    return id[t];

}

int a[];LL f[];

int main()

{

    fac[]=,fac_inv[]=;

    for(int i=;i<=;i++)

        fac[i]=fac[i-]*i%mod,fac_inv[i]=quick_pow(fac[i],mod-);

    scanf("%d",&n);

    for(int i=;i<n;i++)scanf("%d",&a[i]);

    z=;dfs(,);

    sort(mp+,mp+z+,cmp);

    for(int i=;i<=z;i++)id[mp[i]]=i;

    memset(f,,sizeof(f));f[]=;

    for(int zt=;zt<=z;zt++)

        if(f[zt]>)

        {

            int e=n-mp[zt].u[]+;//轮到第几条边用来合并

            LL P=getP(mp[zt].getsum()-(a[e-]),a[e]-a[e-]-);//两条树边中间其他边选择的方案数 

            for(int i=;i<=mp[zt].u[];i++)

                for(int j=i+;j<=mp[zt].u[];j++)

                {

                    int nzt=getnzt(zt,i,j);

                    f[nzt]=(f[nzt]+f[zt]*P%mod*mp[zt].u[i]%mod*mp[zt].u[j]%mod)%mod;

                }

        }

    int rst=n*(n-)/-a[n-];

    printf("%lld\n",f[z]*getP(rst,rst)%mod);

    return ;

}

巴特西

NOI.AC #31. MST

最新文章

热门文章