题目链接：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}\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; ll ans=1; int main() { n=read(); for(int i=1;i<=n;i++)m+=read(); for(int i=1;i<=m;i++)if(i!=m-n+1)(ans*=i)%=998244353; printf("%lld\n",ans); } |
Comments | 7 条评论
傻逼你注册功能啥时候修啊
真是令人头大
@王奕然 姜 : 傻逼你不是都有账号了吗
@王奕然 姜 : 有生之年，如果我闲得没事就修了
@l1ll5 : 那你把公告改改啊，省着欺骗大家感情
@王奕然 姜 : 你这评论功能也挺傻逼的，还得点一下显示评论
然后评论完了还不自动刷新
真是令人头秃
(ಡωಡ)
@GXZlegend : 你有没有看到我发那个 cf 里的半平面查询的做法啊-_-