清华大学生命科学博士就业_已拥有的是全部的生命

清华大学生命科学博士就业_已拥有的是全部的生命不错的组合数学题。同时这也驱使我去看积灰好久的《具体数学》(看了yu大的blog后)。然后看得头秃……得到一个不等式前缀和大于等于取了的个数。所以如果把每个卡的值减一,问题就变成了求一个排列,使得前

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

不错的组合数学题。同时这也驱使我去看积灰好久的《具体数学》(看了yu大的blog后)。然后看得头秃……

得到一个不等式前缀和大于等于取了的个数。所以如果把每个卡的值减一,问题就变成了求一个排列,使得前缀和都非负。

\[\forall i, \mathbf{s.t.} a_1 + a_2 + \dots + a_i \geq 0 \]

显然 \(\sum a_i = 0\)

看样子很难搞。

可以发现,如果把序列循环位移,可能会得到新的方案,那么对每个环进行计算。

但是环可能会贡献多个值,如果这么做,答案就是 \(\sum_{C} f\left(C\right)\),其中 \(C\) 是圆排列, \(f\left(C\right)\) 是断环的方式数,使得前缀和大于等于 \(0\),也等价于找到一个合法的断环方式,此时 \(f\left(C\right)\) 就是使得部分和为 \(0\) 的位置数。

这不就是定义吗?显然一个环的多个贡献给我们的计数造成了麻烦。

考虑转换一下,使环的贡献只能是 \(1\)

如果见过 \(\texttt{Raney}\) 引理,就会发现一个类似的地方:

下面摘自《具体数学》301页 原话:

如果 \(\left< x_1, x_2, \dots , x_m \right>\) 是任何一个其和为 \(+1\) 的整数序列,那么它的循环移位

\[\left< x_1, x_2, \dots , x_m \right>,\left< x_2, \dots ,x_m,x_1 \right>,\dots,\left< x_m, x_1,\dots ,x_{m-1} \right> \]

中恰好有一个满足所有的部分和都是正数。

可以感性理解一下

然后提供了一个例子,就是往卡特兰数计数时,序列最前面加一个 \(1\)。然后容易计数。

这道题的部分和非负,如果在序列前面加个 \(1\),不就是 \(\texttt{Raney}\) 引理了?

我们考虑像这个引理一样,在序列头加一个 \(1\),可以发现,并不是所有地方都能加,例如 \(2,-1,-1\),如果在 \(2\) 后面加 \(1\) 显然是不行的。然后发现加的方案数正好和上面的 \(f\left( C\right)\) 一样——这不是加了跟没加一样?

但是不用担心,我们考虑黑科技,不加 \(1\),改成加 \(-1\)

我们往原序列里插入一个 \({-1}^*\) ,此时问题转换为对圆排列找出一种断环方式,使得前 \(m\) 个的部分和非负,并且元素和为 \(-1\)

易证最后一个必定是 \(-1\),并且用类似方法可以证明一定存在且仅存在一个满足条件的断环方式。(我不会证,逃

由于有标号,有 \(m – n + 1\)\(-1\),于是最后一个 \(-1\) 就有 \(m – n + 1\) 种标号。我们要钦定最后一个 \(-1\)\({-1}^*\),所以答案要除以 \(m – n + 1\)

\(m + 1\) 个元素的圆排列方案数为 \(m!\),于是答案就是 \(\frac{m!}{m – n + 1}\)

复杂度 \(O\left(m\right)\),可以通过此题。

使用快速阶乘可以得到更低的复杂度以及更大的常数。

#include <bits/stdc++.h>

const int mod = 998244353;
typedef long long LL;
int n, m;
int main() {
	std::cin >> n;
	for (int i = 1, t; i <= n; ++i) std::cin >> t, m += t;
	int ans = 1;
	for (int i = 2; i <= m; ++i)
		if (i != m - n + 1)
			ans = (LL) ans * i % mod;
	std::cout << ans << std::endl;
	return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/167479.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • flask jsonify之序列化时的default函数、jsonify序列化自定义对象[通俗易懂]

    flask jsonify之序列化时的default函数、jsonify序列化自定义对象[通俗易懂]目录1.看源码2、重写默认的default函数,实现自己的序列化机制3、把对象转化成字典3.1__dict__的方式3.2、定义keys和__getitem__的方式4、最终的代码实现5、关于default函数的其他知识1.看源码打开site-package,flask,json,__init__.pyjsonify回去调用default()函数,我们…

  • 俞敏洪 绝望中寻找希望_新东方俞敏洪哭了

    俞敏洪 绝望中寻找希望_新东方俞敏洪哭了                                新东方俞敏洪:从绝望中寻找希望                         http://www.sina.com.cn  2008年08月23日 10:25  华夏时报 .moduleSingleImg01img{border:1pxsolid#D1E3F4} –>

  • MATLAB中meshgrid函数用法

    MATLAB中meshgrid函数用法meshgrid是MATLAB中用于生成网格采样点的函数。在计算机中进行绘图操作时,通常会给出如z=x^2+y^2会给出表格数据,涉及到x、y、z三组数据,而x、y这两组数据可以看做是在Oxy平面内对坐标进行采样得到的坐标对(x,y)。表中一共有7*7=49个数据,我们分别标出来,得到下图 试问如何用MATLAB函数画出此图

  • Windows 下Maven安装配置(本地仓库配置)[通俗易懂]

    Windows 下Maven安装配置(本地仓库配置)[通俗易懂]一、下载mavenmaven官网:http://maven.apache.org/下载下来也就是一个压缩文件,解压。我下载的是3.5.2版本,解压之后如下:路径为:D:\ProgramFiles\apache-maven-3.5.2二、配置环境变量添加自定义变量:MAVEN_HOME值为刚才的解压路径:D:\ProgramFiles\apache-maven-3.5.2。MAVEN_

  • Python如何运行程序

    Python如何运行程序Python解释器简介解释器是一种让其他程序运行起来的程序。Python也有一个名为解释器的软件包,当你编写了一段Python程序,Python解释器将读取程序,并按照其中的命令执行,得出结果。实际

  • 全国各地运营商dns列表(供查询)

    全国各地运营商dns列表(供查询)DNS列表 省份 城市 中国电信 中国联通 中国移动 教育网 云南 昭通 222.172.200.68 61.166.150.123 221.3.131.11 221.3.131.12 211.139.29.170 202.203.66.3

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号