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

发布于 2018-01-07  216 次阅读


题目链接: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}\)

 


一个非常弱的准退役OIER