bzoj4735 你的生命已如风中残烛

bzoj4735 你的生命已如风中残烛

​​ Description 众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习。但是今天六花酱不想做数学题，于是他 们开始打牌。现在他们手上有m张不同的牌，牌有两种：普通牌和功能牌。功能牌一共有n张，每张功能牌都有一个 属性值wi，保证Sigma(wi)=m,1<=i<=N现在勇太将这m张牌随机打乱（一共有m!种不同的顺序）。一开始，六花先从 牌堆顶端取一张牌。接着每回合六花可以选择手中的一张牌打出，如果这张牌是普通牌，那么什么都不会发生；如 果这种牌是功能牌，那么六花需要从牌堆顶端再取wi张牌。重复这个过程直到六花手中没有手牌或六花要摸牌的时 候牌堆已经空了，如果是前者，则勇太胜利，否则六花胜利。举例来说，如果牌堆是{3，0，2，0，0）（用0表示 普通牌，其他数字表示wi），那么六花打牌的过程可以为： 1)取一张牌，手中的牌为{3}。 2)打出{3}，再取三张牌，手中的牌为{0，2，0}。 3)打出这三张牌，还需要再取两张，取到第二张的时候牌堆中已没有牌，六花胜利。 而如果牌堆是{2，0，0，3,0}，不难发现是勇太大胜利。现在，六花想要知道，这M!种顺序中，有多少种是能让自 己取得胜利的呢。当然这个问题对萌萌哒六花来说实在是太雉了，所以她来向你寻求帮助，你能帮帮她吗。 Input 第一行一个整数n。 第二行他个空格隔开的正整数wi。 通过输入你可以自己算出来m=Sigma(Wi),1<=i<=N n≤40，1< wi≤10^5 Output 输出一个整数表示答案，答案可能很大，你只需要输出对998244353取模后的结果。 Sample Input 1 3 Sample Output 2 样例解释一 m!种牌堆中，{3，0，0），{0，3，0）{0，0，3）各有两个，其中只有第一种满足条件。 HINT

Source 好难想 想了一上午..

考虑每个数都-1 然后这样只需要保证所有的前缀和都>=0即可 那么我们考虑 将序列写成圆排列的形式 然后去切刀 看什么情况满足条件 首先圆排列的计算公式是m! 但是因为 我每个-1切刀可以看做相同的 所以

可以证明 一定只存在一个 首先存在性的证明可以考虑反证 即因为不妨假设加法的地方看做加油点 所有的油量够跑完全程 但是如果枚举一个地方 发现不够跑那么就换一个地方 如果发现所有都不行就和原来的矛盾了 唯一性 同理证明即可

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int mod=998244353;int n,m,ans;int main(){ freopen("bzoj4735.in","r",stdin); n=read();ans=1; for (int i=1;i<=n;++i) m+=read(); for (int i=2;i<=m;++i){ if (i!=m-n+1) ans=(ll)ans*i%mod; }printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。