BZOJ4735:你的生命已如风中残烛(组合数学)
2024-10-16 12:01:49
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
3
Sample Output
2
样例解释一
m!种牌堆中,{3,0,0),{0,3,0){0,0,3)各有两个,其中只有第一种满足条件。
样例解释一
m!种牌堆中,{3,0,0),{0,3,0){0,0,3)各有两个,其中只有第一种满足条件。
Solution
六花真是太可爱了
答案是$\frac{m!}{m-n+1}$。
假设所有的数都减$1$,然后在序列末尾添上一个$-1$。也就是要保证所有的前缀和大于等于$0$。
把这个序列头尾相接成一个环,$m+1$个数圆排列的个数为$m!$。
画个图感性理解一下可以发现每个圆排列只有一种断法。
又因为我们一开始加了一个$-1$,而这个$-1$可能是$n-m+1$个$-1$里面的任意一个,所以要除掉。
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
#define MOD (998244353)
using namespace std; LL n,m,ans=; inline int read()
{
int x=,w=; char c=getchar();
while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}
while (c>='' && c<='') x=x*+c-'', c=getchar();
return x*w;
} int main()
{
n=read();
for (int i=; i<=n; ++i) m+=read();
for (int i=; i<=m; ++i)
if (i!=m-n+) (ans*=i)%=MOD;
printf("%lld\n",ans);
}
最新文章
- C#设计模式-状态者模式
- 【转】Django Model field reference学习总结
- struts2类型转换
- 洛谷 P1026 统计单词个数 Label:dp
- json_decode返回null 和synax error原因及处理
- 用typedef自定义类型语法你真的会吗
- DateTime , DateTime2 ,DateTimeOffset 之间的小区别
- jQuery 中 attr() 和 prop() 方法的区别
- python :页面布局 ,后台管理页面之左侧菜单跟着滚动条动
- bootstrap-5
- MVC 学习系列-Controller
- (二). 细说Kalman滤波:The Kalman Filter
- Qt 窗口等设置
- mysql之触发器trigger(1)
- bootstrap之WaitForIdle&;amp;&;amp;Clear
- 基于Debian系统配置Nginx环境的Node.js应用教程
- 基于ELK的数据分析实践——满满的干货送给你
- 常量和静态变量会先载入内存后在进行执行php代码
- python 文本比对
- 学以致用三十四-----python2.0加载图片
热门文章
- 9.C#知识点:线程初识及Thread初识(一)
- elasticsearch6.7 05. Document APIs(2)Index API
- 【mysql】连接的空闲时间超过8小时后 MySQL自动断开该连接解决方案
- 什么是 Spring AOP 和代理
- js字符串如何倒序
- CSS3实现的几个小loading效果
- Spring AOP 中@Pointcut的用法
- Zookeeper简单初应用
- 5,注释、分支结构、循环结构、伪&ldquo;选择结构&rdquo;
- .NET(C#)使用Serialize、Deserialize序列和反序列化XML文档