题目连接
题目概述
有(n)个人,为了完成一项任务,可以从这(n)个人组成的子集中选择一个来完成这个任务,对于选出的这个包含有(k)个人的子集,需要付的费用是(x^k),求对于这个(n)个人组成的非空子集需要付的总费用是多少,即求这个结果
其中(n)的范围是(1leq 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)进行展开,再<组合数学>这本书里面,再将差分序列时曾经给出一个定理:
这里的(S(p,i))就是第二类(Stirling)数,然后用这个展开(i^k)得到:
这里面的第二类(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(klog(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
", ans);
}
int main(int argc, const char** argv) {
calculate_Stirling();
int n, k;
scanf("%d%d", &n, &k);
calculate(n,k);
return 0;
}