题目连接

CF932E

题目概述

        有$n$个人,为了完成一项任务,可以从这$n$个人组成的子集中选择一个来完成这个任务,对于选出的这个包含有$k$个人的子集,需要付的费用是$x^k$,求对于这个$n$个人组成的非空子集需要付的总费用是多少,即求这个结果
$\sum_{i=1}^n{C_n^i i^k}$
其中$n$的范围是$1\leq n \leq 10^9$,$k$的范围是$1 \leq k \leq 5000$,因为结果很大,所以对于最后输出的结果要模$10^9+7$.

基础解法

        首先这个$N$的规模非常大,所以尝试直接求$C_n^i$的方法是不现实的,虽然有一个$\frac{C_n^i}{C_n^{i-1}}=\frac{n-i+1}{i}$递推式,但是用这个算的话也是$O(n)$,而且算的过程要处理除法的取模,应该是我处理的方法不对,所以提交上去总是WA.出题人给的题解使用微分和dp的方法,$(1+x)^n$展开式.

        出题人给的那个dp的解决方法没看懂,然后去洛谷上看了一下,对于这题的思路都是利用第二类$Stirling$数对$i^k$进行展开,再<组合数学>这本书里面,再将差分序列时曾经给出一个定理:
$\begin{aligned}N^p &=\sum_{i=0}^n{c(p,i)C_n^i} \\&=\sum_{i=0}^n{\frac{c(p,i)}{i!}P_n^i}\\&=\sum_{i=0}^n{S(p,i)P_n^i} \end{aligned}$

这里的$S(p,i)$就是第二类$Stirling$数,然后用这个展开$i^k$得到:
$\begin{aligned}\sum_{i=1}^n{C_n^i i^k} &= \sum_{i=1}^n{C_n^i \sum_{j=0}^k{S(k,j)C_i^jj!}}\\&= \sum_{i=0}^n{C_n^i \sum_{j=0}^k{S(k,j)C_i^jj!}}\qquad(C_n^0 0^k = 0)\\&= \sum_{i=0}^n{\sum_{j=0}^k{S(k,j)\frac{n!i!j!}{i!(n-i)!j!(i-j)!}}}\\&= \sum_{i=0}^n{\sum_{j=0}^k{S(k,j)\frac{n!}{(n-i)!(i-j)!}}}\\&= \sum_{i=0}^n{\sum_{j=0}^k{S(k,j)\frac{n!(n-j)!}{(n-i)!(i-j)!(n-j)!}}} \qquad (n-i+i-j = n-j) \\&=\sum_{i=0}^n{\sum_{j=0}^k{S(k,j)\frac{n!}{(n-j)!}\frac{(n-j)!}{(n-i)!(i-j)!}}}\\&=\sum_{j=0}^k{S(m,j)\frac{n!}{(n-j)!}\sum_{i=0}^n{\frac{(n-j)!}{(n-i)!(i-j)!}}} \qquad(将上一个式子里面连加的部分内容提到外边)\\&=\sum_{j=0}^k{S(k,j)\frac{n!}{(n-j)!}\sum_{i=0}^n{C_{n-j}^{n-i}}} \qquad( n-j \leq n, 0 \leq n-i\leq n)\\&=\sum_{j=0}^k{S(k,j)\frac{n!}{(n-j)!}2^{n-j}} \qquad( 1 \leq k \leq 5000) \end{aligned}$

这里面的第二类$Stirling$可以利用递推式$S(n,k) = kS(n-1,k) + S(n-1, k-1),S(0,0)=1,S(k,0)=0$计算,时间复杂度为$\Theta(k^2)$;对于$\frac{n!}{(n-j)!} = n(n-1)\cdots(n-j+1)$,如果放在求和的循环中算的话,需要$\Theta(k)$次;$2^{n-j}$利用快速幂计算,最多的依次计算需要$\Theta(\log(n))$,计算$k$次,总共需要$\Theta(k\log(n))$次.所以总的时间复杂度是$\Theta(k^2)+\Theta(k(O(1)+\Theta(\log(n)))=\Theta(k^2)$.

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005;
const int M = 1e9 + 7;
ll S[N][N];// 计算第二类Stirling数
void calculate_Stirling(){S[0][0] = 1;for(int i = 1; i < N; i++){for(int j = 1; j < i + 1; j++){S[i][j] = ((j * S[i - 1][j]% M) + S[i - 1][j - 1] % M) % M;}}}// 快速乘法取模
ll fast_mul_mod(ll a, ll b){ll ans = 0;while( b > 0){if( b & 1){ans += a;ans %= M;}b >>= 1;a += a;a %= M;}return ans;
}// 快速幂取模
ll fast_exp_mod(int a,int n){ll ans = 1;while( n > 0){if( n & 1 ){ans = fast_mul_mod(ans,a);}n >>= 1;a = fast_mul_mod(a, a);}return ans;
}// 计算结果
void calculate(int n,int k){ll ans = 0;ll fact = 1;for (int i = 0; i <= k; ++i){ll temp = fast_mul_mod(fact, fast_exp_mod(2, n - i));temp = fast_mul_mod(temp,S[k][i]);ans = (ans + temp) % M;// 在循环中计算n!/(n-j)!,1,n,n*(n-1),......fact = fast_mul_mod(fact, n-i);}printf("%lld\n", ans);
}int main(int argc, const char** argv) {calculate_Stirling();int n, k;scanf("%d%d", &n, &k);calculate(n,k);return 0;
}

补充

出题人题解及相应讨论

洛谷大神的$\Theta(k)$解法