第二类斯特林数

组合数学 / 题解

洛谷题库 P6031 Cards 加强版 – 题解与思路重现

洛谷题库 P6031 Cards 加强版

对于每一轮对局的 m!m! 种排列，对于编号为 aa 的牌，恒有 (m−1)!(m-1)! 种是以牌 aa 为首的。因此一轮可以归为 mm 种情况，首张为王牌的概率为 1m\frac{1}{m}。

这是某场模拟考试给出的部分分： SubtaskConstraintsPointsDependencies1n,m,k≤522k=123k≤5000101,24m≤1001015n≤k56k≤105101,2,37k≤5×106201,2,3,68411∼7 \begin{array}{cccc} \text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline 1&n,m,k\leq 5&2&\\ 2&k=1&2&\\ 3&k\leq 5000&10&1,2\\ 4&m\leq 100&10&1\\ 5&n\leq k&5&\\ 6&k\leq 10^5&10&1,2,3\\ 7&k\leq 5\times 10^6&20&1,2,3,6\\ 8&&41&1\sim 7 \end{array} （更多…）

More
  • 2023年1月31日
未分类

一个二项式式子的推导 兼 CF1716F – Bags with Balls 题解与思路重现

Educational Codeforces Round 133 F – Bags with Balls

题目中存在高次项的和。则我们分别计算有 p=1,2,⋯ ,np=1,2,\cdots,n 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子，每个有 ⌈m2⌉\lceil \frac{m}{2} \rceil 种选择；偶数的则有 ⌊m2⌋\lfloor \frac{m}{2} \rfloor 种。因此答案为： ∑p=0npk(np)⌈m2⌉p⌊m2⌋n−p \sum_{p=0}^{n}p^k\dbinom{n}{p}\Big\lceil\frac{m}{2}\Big\rceil^p\Big\lfloor \frac{m}{2} \Big\rfloor^{n-p}

由于 n≤109n\leq 10^9，这式子看起来非常棘手。但我们注意到，有 k≤2000k\leq 2000，这提示我们或许应该转变对答案的贡献方式：从高次幂入手，找到 O(poly⁡k)\mathrm{O}(\operatorname{poly} k) 而非 O(n)\mathrm{O}(n) 的算法。 （更多…）

More
  • 2022年8月8日
成都外国语学校高二 OIer。喜欢搞些杂七杂八的小项目。常去骑车。复健中，脚力已不如前。

一言(ひとこと)

暫し空に祈りて 愛を断て

分类目录