Luogu2791 幼儿园篮球题【斯特林数，数学】

女爷i 2021-11-09 11:02 262阅读 0赞

题目链接：[洛谷][Link 1]

我一开始不知道$N,M$有什么用处，懵逼了一会儿，结果才发现是输入数据范围。。。

$$\\begin\{aligned\}\\binom\{n\}\{k\}Ans&=\\sum\_\{i=0\}^k\\binom\{m\}\{i\}\\binom\{n-m\}\{k-i\}i^L \\\\&=\\sum\_\{i=0\}^k\\binom\{m\}\{i\}\\binom\{n-m\}\{k-i\}\\sum\_\{j=0\}^Lj!\\binom\{i\}\{j\}\\begin\{Bmatrix\}L \\\\ j\\end\{Bmatrix\} \\\\&=\\sum\_\{j=0\}^Lj!\\begin\{Bmatrix\}L \\\\ j\\end\{Bmatrix\}\\sum\_\{i=0\}^k\\binom\{m\}\{i\}\\binom\{n-m\}\{k-i\}\\binom\{i\}\{j\} \\\\&=\\sum\_\{j=0\}^Lj!\\begin\{Bmatrix\}L \\\\ j\\end\{Bmatrix\}\\sum\_\{i=0\}^k\\binom\{m\}\{j\}\\binom\{m-j\}\{i-j\}\\binom\{n-m\}\{k-i\} \\\\&=\\sum\_\{j=0\}^L\\frac\{m!\}\{(m-j)!\}\\begin\{Bmatrix\}L \\\\j\\end\{Bmatrix\}\\sum\_\{i=0\}^k\\binom\{m-j\}\{i-j\}\\binom\{n-m\}\{k-i\} \\\\&=\\sum\_\{j=0\}^L\\frac\{m!(n-j)!\}\{(k-j)!(n-k)!(m-j)!\}\\begin\{Bmatrix\}L \\\\j\\end\{Bmatrix\}\\end\{aligned\}$$

所以答案

$$Ans=\\frac\{m!k!\}\{n!\}\\sum\_\{i=0\}^\{\\min(L,m,k)\}\\frac\{(n-i)!\}\{(m-i)!(k-i)!\}\\begin\{Bmatrix\}L \\\\ i\\end\{Bmatrix\}$$

上面第五行到第六行使用了范德蒙德卷积

$$\\sum\_\{i=0\}^k\\binom\{n\}\{i\}\\binom\{m\}\{k-i\}=\\binom\{n+m\}\{k\}$$

组合意义：在$n+m$个元素中取$k$个，前$n$个元素中选了$i$个。

而且要注意$i$的范围，不然就会挂成15分

时间复杂度$O(L(\\log L+S))$。

转载于:https://www.cnblogs.com/AThousandMoons/p/11210018.html

[Link 1]: https://www.luogu.org/problemnew/show/P2791

发表评论取消回复

表情：

评论列表（有 0 条评论，262人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu2643（第二类斯特林数） Rank

Rank Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

以你之姓@/ 2024年02月18日 14:32/ 0 赞/ 39 阅读

相关 hdu4372（第一类斯特林数） Count the Buildings

Count the Buildings Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536

骑猪看日落/ 2024年02月18日 14:31/ 0 赞/ 33 阅读

相关斯特林数 HDU 3625

/ 斯特林数第一类 n个元素的集合分成k个环排列的方法 s[n][0] = 0; s[1][1] = 1; s[n][

短命女/ 2022年09月29日 04:24/ 0 赞/ 145 阅读

相关 Hdu 4045 Machine scheduling (组合数，斯特林数)

11年北京网络赛的题目题意：有N个机器，每天选出R个机器，而且每两个机器的编号差要大于等于K，每天将这R个机器最多分为M组工作，问最多有多少种方案。思路：问题由两部分构

不念不忘少年蓝@/ 2022年09月17日 11:14/ 0 赞/ 174 阅读

相关求N!的位数（斯特林公式）

斯特林公式 lnN!=NlnN-N+0.5\ln(2\N\pi) 要想求有多少位，将他换成以10为底便可！利用换底公式得 lnN!/ln10=log10N!

拼搏现实的明天。/ 2022年08月04日 09:15/ 0 赞/ 197 阅读

相关 ACM 斯特林公式 Factorial vs Power

斯特林公式（Stirling's approximation）是一条用来取n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而

约定不等于承诺〃/ 2022年06月12日 12:48/ 0 赞/ 180 阅读

相关【组合数学】第二类斯特林数

一、定义第二类Stirling数即:![SouthEast][]，又可记为![SouthEast 1][]\[与第一类的表示有大小写的区别\]。其表示将n个不同的元素分成

雨点打透心脏的1/2处/ 2022年06月01日 04:57/ 0 赞/ 545 阅读

相关 51Nod1130斯特林近似

![1575943-20190227195117036-288323810.jpg][] log10(n!)=log10(2\pi\n)\0.5+n\log10(n/e)

Dear 丶/ 2022年01月10日 06:43/ 0 赞/ 206 阅读

相关 Luogu2791 幼儿园篮球题【斯特林数，数学】

题目链接：[洛谷][Link 1] 我一开始不知道$N,M$有什么用处，懵逼了一会儿，结果才发现是输入数据范围。。。 $$\\begin\{aligned\}\\binom

女爷i/ 2021年11月09日 11:02/ 0 赞/ 263 阅读

相关 POJ 1423 斯特林

题意：进制问题分析：打表，但是要用不能 long long 型，超内存。 n! = log\_\{10\}\\sqrt\{2\{\\pi\}n\}\(\\f

素颜马尾好姑娘i/ 2021年09月30日 11:44/ 0 赞/ 316 阅读