主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
构式构造（P5441）
最后更新于 2025-08-27 17:50:13
作者
q1uple
分类
题解
题解
P5441
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
观前提示：本文只是一个笔者能够自己做出来本题的思考，如果想学习严谨证明请观看其他题解。 感觉是很精妙的问题。 考虑这样一种构造。 $$1\to 2,2\to3 \dotsb n\to 1$$ 上面是双向边的构造。 考虑其他边是怎样连的，一种很直接的想法就是 $\forall i,j,i<j$ 那么就有一条 $(i,j)$ 的边。但是这实际上是错的。那我们怎么办呢？ 考虑这样一种连边方式按照 $i+j$ 的奇偶性看是 $(i,j)$ 这种边，还是$(j,i)$。我们将他们称为黑/白边。 为什么是对的，感性理解上是因为这样可保证走过去再绕回来。类似于黑白染色。 我们已经构造出来了一种方式，但是还要考虑方案数。 考虑讨论从一个点出发，对于三个出边的奇偶性进行讨论。 这里可以可以钦定节点的编号大小是 $i<j<k<l$，然后你本地爆搜跑一下枚举他的奇偶性，是可以做的，跑出来只有 $8$ 种是合法的，恰好是一半。 那我们的对于一个点的答案就是 ${\frac{n-3}{2}r \choose 3}$，为什么，你考虑这样一个事情。你一次能选的是不是就是只有 $\frac{n-3}{2}$ 种，因为排除了双向边和本身。 现在我们在考虑双向边，如果四个点之间都是双向边链接肯定合法，那么三个点和两个点呢？，根据我们的构造和抽屉原理，他们肯定是又有偶数还有奇数的，所以不存在！！！ 所以答案是 ${n\choose 4}- n{\frac{n-3}{2}\choose 3}$
正在渲染内容...
点赞
0
收藏
0
