NOI.AC 31 MST——整数划分相关的图论(生成树、哈希)[通俗易懂]

NOI.AC 31 MST——整数划分相关的图论(生成树、哈希)[通俗易懂]NOI.AC 31 MST——整数划分相关的图论(生成树、哈希)

大家好,又见面了,我是你们的朋友全栈君。

题目:http://noi.ac/problem/31

模拟 kruscal 的建最小生成树的过程,我们应该把树边一条一条加进去;在加下一条之前先把权值在这一条到下一条的之间的那些边都连上。连的时候要保证图的连通性不变。

已经加了一些树边之后,图的连通性是怎样的呢?这可以是一个整数划分的问题。据说方案只有4万多,所以可以搜一下,搜出有 k 个连通块的方案数。

为了转移和转移时算方案数,还要记录每个方案的:各个连通块的点数,所有的空位(可放边)数。

可以用 map 来存状态。 map 的角标是一个随便哈希的值,map 的值是这个状态的编号,也是这个状态的其他信息在那些数组里的角标。这样要算下一个状态是谁的时候就可以通过记录的“各个连通块的点数”找到”下一个状态的各个连通块的点数“,再用一样的方法哈希起来,利用 map 就能找到下一个状态的编号了。

因为不太会写,所以就学习(抄)了一下别人的。

1.注意算排列时判 n<m !数组越界本地可能答案正确,但交上去就会爆。

2.不知 1e4 是怎么确定的?

3.学题解 N=41 WA了最后两个点,改成45就A了。不知为何。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=45,M=1e4,mod=1e9+7,base=M;//N=41会WA两个点?!
int n,a[N],cd[N],vec[N][M][N],edg[N][M];//N的情况里第M个的 空位/第N个连通块的点数
int dp[N][M],lm,tmp[N],id[N][N],tmpx[N],top;
int jc[N*N],jcn[N*N];
ull hsh;
map<ull,int> mp[N];//用值得到另一个角标(cd)
int rdn()
{
    int ret=0;bool fx=1; char ch=getchar();
    while(ch>'9'||ch<'0'){
   
   if(ch=='-')fx=0; ch=getchar();}
    while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
    return fx?ret:-ret;
}
int pw(int x,int k)
{
    int ret=1;while(k){
   
   if(k&1ll)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1ll;}return ret;
}
void init()
{
    lm=(n*(n-1)>>1);//not n
    jc[0]=1;
    for(int i=1;i<=lm;i++) jc[i]=(ll)jc[i-1]*i%mod;
    jcn[lm]=pw(jc[lm],mod-2);
    for(int i=lm-1;i>=0;i--) jcn[i]=(ll)jcn[i+1]*(i+1)%mod;
}
void dfs(int sm,int cr,int lst)
{
    if(lst*(lm-cr+1)>sm) return;
    if(cr>lm)
    {
        hsh=0;
        for(int i=1;i<cr;i++)hsh=hsh*base+tmp[i];
        mp[lm][hsh]=++cd[lm];
        for(int i=1;i<cr;i++)
        {
            vec[lm][cd[lm]][i]=tmp[i];
            edg[lm][cd[lm]]+=(tmp[i]*(tmp[i]-1)>>1);
        }
        //printf("edg[%d][%d]=%d\n",lm,cd[lm],edg[lm][cd[lm]]);
        return;
    }
    if(cr==lm)
    {
        tmp[cr]=sm;dfs(0,cr+1,0);//有剪枝,所以一定不降
        return;
    }
    for(int i=lst;i<=sm;i++)
    {
        tmp[cr]=i;
        dfs(sm-i,cr+1,i);
    }
}
int P(int n,int m)
{
    if(n<m) return 0;//!!!!!!
    //printf("jc[%d]=%d jcn[%d]=%d\n",n,jc[n],n-m,jcn[n-m]);
    return (ll)jc[n]*jcn[n-m]%mod;
}
int main()
{
    n=rdn();
    init();
    for(int i=n;i>1;i--) a[i]=rdn(); a[1]=(n*(n-1)>>1);
    for(int i=1;i<=n;i++) lm=i,dfs(n,1,1);
    dp[n][1]=1;
    for(int i=n;i>1;i--)
        for(int s=1;s<=cd[i];s++)
        {
            //printf("y dp[%d][%d]=%d\n",i,s,dp[i][s]);
            //printf("%d-%d=%d %d-%d-1=%d\n",edg[i][s],a[i+1],edg[i][s]-a[i+1],a[i],a[i+1],a[i]-a[i+1]-1);
            dp[i][s]=(ll)dp[i][s]*P(edg[i][s]-a[i+1],a[i]-a[i+1]-1)%mod;
            //printf("now dp[%d][%d]=%d(P=%d)\n",i,s,dp[i][s],P(edg[i][s]-a[i+1],a[i]-a[i+1]-1));
            memset(id,0,sizeof id);
            for(int j=1;j<=i;j++)tmp[j]=vec[i][s][j];
            for(int u=1;u<=i;u++)
                for(int v=u+1;v<=i;v++)//哪两个集合
                {
                    //printf("i=%d s=%d tmp[%d]=%d tmp[%d]=%d\n",i,s,u,tmp[u],v,tmp[v]);
                    if(!id[tmp[u]][tmp[v]])
                    {
                        top=0;
                        for(int p=1;p<=i;p++)
                            if(p!=u&&p!=v)tmpx[++top]=tmp[p];
                        tmpx[++top]=tmp[u]+tmp[v];
                        for(int p=top-1;p;p--)//插排
                            if(tmpx[p]>tmpx[p+1])swap(tmpx[p],tmpx[p+1]);
                            else break;//else
                        hsh=0;
                        for(int p=1;p<=top;p++)
                            hsh=hsh*base+tmpx[p];
                        id[tmp[u]][tmp[v]]=mp[i-1][hsh];
                        //printf("id[%d][%d]=%d\n",tmp[u],tmp[v],id[tmp[u]][tmp[v]]);
                    }
                    dp[i-1][id[tmp[u]][tmp[v]]]=
                        (dp[i-1][id[tmp[u]][tmp[v]]]+(ll)dp[i][s]*tmp[u]*tmp[v])%mod;
                    //printf("dp[%d][%d]=%d(dp=%d tmu=%d tmv=%d)\n",i-1,id[tmp[u]][tmp[v]],dp[i-1][id[tmp[u]][tmp[v]]],dp[i][s],tmp[u],tmp[v]);
                }
        }
    //printf("%d-%d=%d %d-%d-1=%d\n",edg[1][1],a[2],edg[1][1]-a[2],a[1],a[2],a[1]-a[2]-1);
    dp[1][1]=(ll)dp[1][1]*P(edg[1][1]-a[2],a[1]-a[2]-1)%mod;
    printf("%d\n",dp[1][1]);
    return 0;
}

 

转载于:https://www.cnblogs.com/Narh/p/9675064.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107298.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号