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

清华大学生命科学博士就业_已拥有的是全部的生命不错的组合数学题。同时这也驱使我去看积灰好久的《具体数学》(看了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)


相关推荐

  • 用python画一个爱心_python 画一个点

    用python画一个爱心_python 画一个点fromturtleimport*pensize(1)pencolor(‘red’)fillcolor(‘pink’)speed(5)up()goto(-30,100)down()begin_fill()left(90)circle(120,180)circle(360,70)left(38)circle(360,70)circle(120,180)end_fill()up()goto(-100,-100)down()

  • 挖矿病毒清除记录

    挖矿病毒清除记录转载地址:https://www.52pojie.cn/thread-864849-1-1.html?tdsourcetag=s_pctim_aiomsg起因是同学过年期间因阿里云的服务器Redis弱口令(好像是没设密码)被提权植入了挖矿病毒,CPU长期占用100%。登录服务器后,首先使用Top命令,查看CPU占用。发现CPU占用率达到100%,可是却没有相关占用高的进程。想…

  • 物联网架构设计「建议收藏」

    物联网架构设计「建议收藏」在设计lan(Github:https://github.com/phodal/lan)物联网平台的时候,结合之前的一些经验,构建出一个实际应用中的物联网构架模型。然后像lan这样的应用,在里面刚属于服务层。物联网层级结构通常,我们很容易在网上看到如下图所示的三层结构:从理论上划分这样的层级结构是没有问题的,也是有各种理…

  • 输入网址访问服务器详细流程

    输入网址访问服务器详细流程问题:以前遇到过一次输入一个网站打不开,该网站服务器没问题,换台电脑可以打开。这台电脑可以打开别的网站,就是打不开我要访问的网站。后来找到C:\Windows\System32\drivers\etc\hosts 这个文件,在该文件中找到该网址删掉就好了. 答案:   输入网址访问的时候,浏览器会进行解析域名,找对应的ip地址。那么首先就从本机C:\Windows\System…

  • C# 哈希_java哈希码

    C# 哈希_java哈希码文件哈希码比较,用于更新文件publicstaticboolCompareFile(stringstr1,stringstr2)    {      stringp_1=str1;      stringp_2=str2;      //计算第一个文件的哈希值      varha

    2022年10月30日
  • Silverlight游戏设计(Game Design):(十四)练习用游戏素材资源的获取及相关工具使用心得…[通俗易懂]

    Silverlight游戏设计(Game Design):(十四)练习用游戏素材资源的获取及相关工具使用心得…[通俗易懂]通过前6节的Demo制作演示,大家应该已经相当熟悉这款Silverlight-2D游戏场景编辑器了;通过它我们可以构建出各种类型的游戏,这也让广大的Silverlight游戏爱好者们变得蠢蠢欲动,近一段时间里有很多朋友询问我游戏素材资源是如何获取的,那么本节我将向大家分享这方面的经验与心得,漂亮的游戏素材配合上不断的游戏编码练习,在成就感中提升自身的游戏设计能力,让我们一同努力吧!推荐一,免费…

发表回复

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

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