选队长

jkouu 97 0

 

问题:有数量为n的一群人,在这群人中随机选择若干人组成一队,再从队员中选出一人当队长。问这样的方案有多少种?(同一队人不同队长算不同方案,同一个队长不同的一队人也算不同方案)

(返回模1000000007的结果,1<=n<=1e9)

解:这道题思路很简单,大家都能很快列出式子:∑kC(n,k)。

于是,我们很快就能写出第一种解法:

private long C(long n, long k){
    long up = n;
    long down = 1;
    long counter = 1;
    while(counter <= k-1){
        up = (up * (n - counter) ) % 1000000007;
        down = (down * (1 + counter) ) % 1000000007;
        counter++;
    }
    return up / down;
}
public long solution(int n){
    long ans = 0;
    long counter = 1;
    while(counter <= n){
        ans = (ans + counter * C(n, counter)) % 1000000007;
        counter++;
    }
    return ans;
}

但是大家也一眼都能看出来,这个解法的复杂度是O(n^2),肯定是会超时的。那么我们得想办法改进它。

首先我们能想到的是,C(n, k)没有必要每次从头算,可以在上一次的基础上得到这次的结果。这样,算法的复杂度就变成了O(n)。解法如下:

public long solution(int n){
    long ans = 0;
    long counter = 1;
    long up = 1;
    long down = 1;
    while(counter <= n){
        up = (up * (n - counter + 1) ) % 1000000007;
        down = (down * counter ) % 1000000007;
        ans = (ans + counter * up / down) % 1000000007;
        counter++;
    }
    return ans;
}

即使这样,算法也难以在Java允许的2秒时间内跑完。所以我们还得继续优化算法。

我们都知道,C(n, k) = C(n, n-k)。这样我们可以进一步把算法复杂度降到O(n/2)。解法如下:

public long solution(int n){
    long ans = 0;
    long counter = 1;
    long up = 1;
    long down = 1;
    while(counter <= n/2){
        up = (up * (n - counter + 1) ) % 1000000007;
        down = (down * counter ) % 1000000007;
        if( counter * 2 < n){
            ans = (ans + n * up / down) % 1000000007;
        }
        else{
            ans = (ans + counter * up / down) % 1000000007;
        }
        counter++;
    }
    return ans + n;
}

但是,即使这样,当n=1e9时,算法还是需要3秒甚至4秒的时间才能跑完。那我们还能再优化吗?

在上面解法的基础上,很难再去做改良了(至少我现在还没有想到改良的地方)。那我们回头再看看最初的思路:∑kC(n,k)。

我们知道,C(n, k) = n! / (k! * (n-k)!),那我们对这个式子进行一点变形:

C(n, k) = n! / (k! * (n-k)!) = (n / k) * ( (n-1)! / ( (k-1)! * ( n-1 - (k-1)) = (n/k) * C(n-1, k-1)

是不是豁然开朗?kC(n, k) 其实就是C(n-1, k-1)

这样一来, 我们就可以得到∑kC(n,k)=n * 2 ^ (n-1)。得到这个规律后,我们就可以把时间复杂度降到O(n/4)、O(n/8)等等了。下面是O(n/4)的解法:

public long solution(int N){
    long ans = 1;
    int n = N;
    switch ((n-1) % 4){
        case 1:
            ans = 2;
            break;
        case 2:
            ans = 4;
            break;
        case 3:
            ans = 8;
            break;
    }
    n--;
    n -= (n) % 4;
    n /= 4;
    while(n > 0){
        ans = (ans * 16) % 1000000007;
        n--;
    }
    return (N * ans) % 1000000007;
}

 

发表评论 取消回复
您必须 [登录] 才能发表评论!
分享