题意

给定 \(n\) 个点的无向带权完全图,边权为 \(1\sim\frac{n(n-1)}{2}\)。对于满足 \(1\leq k\leq n\) 的每个 \(k\) 求出将原图划分成 \(k\) 个组的方案数,满足组间边的权大于组内边的权值,答案对 \(998244353\) 取模。

\(\texttt{Data Range:}1\leq n\leq 1500\)

题解

这个题蛮好的,只是我赛时没有想出来(甚至差点没有看懂题目),果然还是我太菜了/kk

首先从小到大把边加进来,然后可以发现一个结论:一个连通块是满足条件的当且仅当在加完某条边之后这个连通块是一个团。

这个时候可以直接用类似于 Kruskal 的方法:从小到大加边,并查集维护一下这个连通块的大小和边数,当加完某条边时候可以满足这个连通块是一个团的话就标记一下这个连通块是可以的。

这个时候好像是可以 DP 了,但是复杂度会爆炸。

考虑优化一下,在从小到大加边的过程中考虑 Kruskal 重构树。由于重构树新加的节点维护的是一个连通块,其叶子节点是连通块中所有的节点,所以可以对重构树进行 dfs,用一段区间表示一个连通块。

于是现在变成了有一些区间,要从中选出 \(k\) 个覆盖 \(1\sim n\) 的所有位置。把所有区间挂到右端点上,设 \(f_{i,j}\) 表示当前位置为 \(i\) 并且钦定当前最后一个区间右端点为 \(i\),选出了 \(j\) 个区间的答案,转移的时候枚举一下最后一个区间的左端点是什么就没了。

时间复杂度 \(O(n^2\log n)\),主要瓶颈在排序上。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=3e3+51,MOD=998244353;
struct EdgeForKruskal{
ll from,to,dist;
inline bool operator <(const EdgeForKruskal &rhs)const
{
return this->dist<rhs.dist;
}
};
EdgeForKruskal ed[MAXN*MAXN];
ll n,m,idx,u,v,itvc;
ll x[MAXN][MAXN],f[MAXN][MAXN],ffa[MAXN],sz[MAXN],edc[MAXN];
ll l[MAXN],r[MAXN],flg[MAXN];
vector<ll>g[MAXN],itv[MAXN];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline ll find(ll x)
{
return ffa[x]==x?x:ffa[x]=find(ffa[x]);
}
inline void add(ll x)
{
if((++edc[x])==sz[x]*(sz[x]-1)/2)
{
flg[x]=1;
}
}
inline void dfs(ll x)
{
if(x<=n)
{
return (void)(l[x]=r[x]=++itvc);
}
l[x]=n+1;
for(register int to:g[x])
{
dfs(to),l[x]=min(l[x],l[to]);
}
r[x]=itvc,flg[x]?itv[r[x]].push_back(l[x]):(void)1;
}
int main()
{
n=read(),f[0][0]=1;
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=n;j++)
{
x[i][j]=read();
j>i?(void)(ed[++m]=(EdgeForKruskal){i,j,x[i][j]}):(void)1;
}
}
idx=n,sort(ed+1,ed+m+1);
for(register int i=1;i<=n;i++)
{
flg[i]=1,itv[i].push_back(i),ffa[i]=i,sz[i]=1,edc[i]=0;
}
for(register int i=1;i<=m;i++)
{
u=find(ed[i].from),v=find(ed[i].to);
if(u==v)
{
add(u);
}
else
{
g[++idx].push_back(u),g[idx].push_back(v);
ffa[u]=ffa[v]=ffa[idx]=idx;
sz[idx]=sz[u]+sz[v],edc[idx]=edc[u]+edc[v],add(idx);
}
}
dfs(idx);
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=n;j++)
{
for(register int k:itv[i])
{
f[i][j]=(f[i][j]+f[k-1][j-1])%MOD;
}
}
}
for(register int i=1;i<=n;i++)
{
printf("%d ",f[n][i]);
}
}

最新文章

  1. PHP工作笔记:yii2各种功能汇总
  2. 1-02 启动和停止Sql Sever的服务
  3. JavaScript插件架构
  4. Java中的线程池
  5. Python3.5.2官方文档学习备忘录
  6. 细说javascript 中的 window.open() 参数设置
  7. codeforce --- 340D
  8. $parse , $interpolate ,$complie , $destroy
  9. Linux下配置tomcat+apr+native应对高并发
  10. LAMP平台-wordpress的搭建
  11. maven常见问题问答(转)
  12. POJ 3709 K-Anonymous Sequence - 斜率优化dp
  13. DeDeCMS(织梦)变量覆盖0day getshell
  14. 默认情况下eth0网卡配置文件路径及客户端DNS的路径
  15. Python图像处理(14):神经网络分类器
  16. 十九 yield方法
  17. mac上如何卸载node
  18. 设计模式——模板方法模式(TemplateMethod Pattern)
  19. (4)分布式下的爬虫Scrapy应该如何做-规则自动爬取及命令行下传参
  20. haproxy简单配制for mysql

热门文章

  1. JAVA MD5加密算法实现与原理解析
  2. java实现点击查询数据生成excel文件并下载
  3. python中生成随机整数(random模块)
  4. 欧拉函数线性求解以及莫比乌斯反演(Mobius)
  5. 李宏毅老师机器学习第一课Linear regression
  6. C++(VS2015)模板显式特化之template语法深入理解
  7. 网络io控制器
  8. openstack 高可用环境部署(8节点)(一)
  9. filebeat- 配置
  10. linux(centos8):用sort对文本内容排序