CF932E Team Work 第二类斯特林数+组合数学

组合数学"/>

CF932E Team Work 第二类斯特林数+组合数学

文章目录

• 一.题目
• 二.Solution
• 三.Code
• Thanks！

一.题目

有 N ( 1 ≤ N ≤ 1 0 9 ) N(1≤N≤10^9) N(1≤N≤109)个不同的人，你从中选择 x x x( x x x至少为 1 1 1)个人去完成一个团队任务，代价为 x k ( 1 ≤ k ≤ 5000 ) x^k(1≤k≤5000) xk(1≤k≤5000)。
求所有组队方案的总代价。
传送门

二.Solution

不难发现，这道题目可以转化成：
∑ i = 1 n C n i ∗ i k ∑_{i=1}^nC_{n}^{i}∗i^ k i=1∑n​Cni​∗ik
但这要超时，怎么办呢？我们可以通过第二类斯特林数、组合数学、阶乘来分解 i k i^k ik：
i k = ∑ j = 0 k S k j ∗ j ! ∗ C i j i^k=\sum_{j=0}^{k}S_{k}^{j}*j!*C_{i}^{j} ik=j=0∑k​Skj​∗j!∗Cij​
我们可以这样理解：把k个球放进i个盒子里，选择 0 ∼ k 0\sim k 0∼k个盒子放球，每次选 j j j个盒子，把球分成 j j j堆，在给这些堆来一个全排列放进盒子里，就涵盖了所有放球情况。
然后继续来分解：
∑ i = 1 n C n i ∑ j = 0 k S k j ∗ j ! ∗ C i j \sum_{i=1}^{n}C_{n}^{i}\sum_{j=0}^{k}S_{k}^{j}*j!*C_{i}^{j} i=1∑n​Cni