CF932E

题目连接

CF932E

题目概述

????????有\(n\)个人,为了完成一项任务,可以从这\(n\)个人组成的子集中选择一个来完成这个任务,对于选出的这个包含有\(k\)个人的子集,需要付的费用是\(x^k\),求对于这个\(n\)个人组成的非空子集需要付的总费用是多少,即求这个结果

其中\(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\)进行展开,再<组合数学>这本书里面,再将差分序列时曾经给出一个定理:

这里的\(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(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)\)解法

CF932E

原文：https://www.cnblogs.com/2018slgys/p/13284259.html