BZOJ 4735 你的生命已如风中残烛


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4735

题意:见原题面。


解释一下 neither 博客里可能看起来比较让人头大的几个部分。

题意就是说 m 个数,有的是正数,有的是-1,总和为 1,要求有多少种排列方法使得每个前缀和都>=1

考虑在最后添加 1 个-1,就是要除了最后一个地方以外的前缀和都>=1

那么一共有 m+1 个数,环排列有 m! 种

发现 m! 种环排列一一对应原排列当且仅当我们在加入的-1 处切断。

对于每一个环排列的任意一种形态,找到最小的前缀和里最靠后的,那么一定当且仅当把这个位置放到最后才合法

因为这是最小的前缀和里最靠后的,所以一这个位置的下一个位置开始的所有前缀和一定>=1

那么因为再加入一个-1 后总和为 0,所以如果不把这个放最后那么到这个地方就一定会出现<1 的情况

所以对于每种环排列有且仅有一直摆放方法使其合法

这是废话。

最小的前缀和里最靠后的地方一定是个-1,我们一定切这里才合法,同时还得满足这个-1 是我们加入的那个-1 才行。

所以 \(ans=\frac {m!}{m-n+1}\)

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4735 你的生命已如风中残烛


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: