文章目录

一.题目二.Solution三.CodeThanks！

一.题目

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

二.Solution

不难发现，这道题目可以转化成： $$\sum _{i=1}^n{C}_n^i\ast i^k$$ 但这要超时，怎么办呢？我们可以通过第二类斯特林数、组合数学、阶乘来分解$i^k$： $$i^k=\sum _{j=0}^k{S}_k^j\ast j!\ast C_i^j$$ 我们可以这样理解：把k个球放进i个盒子里，选择$0\sim k$个盒子放球，每次选$j$个盒子，把球分成$j$堆，在给这些堆来一个全排列放进盒子里，就涵盖了所有放球情况。 然后继续来分解： $$\sum _{i=1}^n{C}_n^i\sum _{j=0}^k{S}_k^j\ast j!\ast C_i^j$$ $S_k^j$和$j!$对于内层循环是定值，可以提到外面来： $$\to \sum _{j=0}^k{S}_k^j\ast j!\sum _{i=1}^n{C}_n^i\ast C_i^j$$ 然后后面的$C_n^i\ast C_i^j$可以通过组合数的一个性质： $$C_n^m\ast C_m^r=C_n^r\ast C_{n-r}^{m-r}$$

证明： $C_n^m\ast C_m^r$ $=\frac{m!\ast (n-m)!}{n!}\ast \frac{r!\ast (m-r)!}{m!}$ $=\frac{(n-m)!\ast r!\ast (m-r)!}{n!}$ $=\frac{(n-m)!\ast r!\ast (m-r)!\ast (n-r)!}{n!\ast (n-r)!}$ $=\frac{r!\ast (n-r)!}{n!}\ast \frac{(m-r)!\ast (n-m)!}{(n-r)!}$ $=C_n^r\ast C_{n-r}^{m-r}$

于是我们又可以继续推： $$\to \sum _{j=0}^k{S}_k^j\ast j!\ast C_n^j\sum _{i=1}^n{C}_{n-j}^{i-j}$$ 然后让我们来观察一下${\sum }_{i=1}^n{C}_{n-j}^{i-j}$，其实当$i<j$时没有意义，若$i>=j$就将$i-j$视为$t$，则相当于求${\sum }_{t=0}^{n-j}{C}_{n-j}^t$，这显而易见等于$2^{n-j}$，最后就化为： $$\to \sum _{j=0}^k{S}_k^j\ast j!\ast C_n^j\ast 2^{n-j}$$ n太大？我们只用预处理第二类斯特林数，其他的东西跟随着循环递推就行了。So easy！

三.Code

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std; #define LL long long #define M 5005 const LL mod = 1e9 + 7; LL S[M][M], ans, n, k; LL qkpow (LL x, LL y){ LL res = 1; while (y){ if (y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res; } void stirlin2 (int now){ for (int i = 1; i <= now; i ++){ S[i][0] = 0; S[i][i] = S[i][1] = 1; for (int j = 2; j < i; j ++){ S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * 1ll * j % mod) % mod; } } } int main (){ scanf ("%lld %lld", &n, &k); stirlin2 (k); LL C = 1, fac = 1, mi = qkpow (2, n), inv = qkpow (2, mod - 2); for (int i = 1; i <= k; i ++){ C = C * (n - i + 1) % mod * qkpow (i, mod - 2) % mod; fac = fac * i % mod; mi = mi * inv % mod; ans = (ans + S[k][i] * mi % mod * fac % mod * C % mod) % mod; } printf ("%lld\n", ans); return 0; }

Thanks！