题解 | #篮球队#

#include <bits/stdc++.h>
using namespace std;
typedef int_fast64_t INT64;

const int MAX_N = 50;
int n, nums[MAX_N];
INT64 dp[MAX_N * 30000 + 5] = {1};

// 计算最大公约数
int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}

INT64 solve() {
    // 计算GCD并简化数组
    int sum = 0, g = nums[0];
    for(int i = 1; i < n; ++i) {
        g = gcd(g, nums[i]);
    }
    for(int i = 0; i < n; ++i) {
        sum += nums[i] /= g;
    }
    
    // 排序
    sort(nums, nums + n);
    
    // 特殊情况：最大值超过总和一半
    INT64 ans = nums[n-1] > sum/2 ? 1 : 0;
    
    // 动态规划
    for(int i = n-1; i > 0; --i) {
        // 更新dp数组
        for(int j = (sum-1)/2; j >= nums[i]; --j) {
            dp[j] += dp[j - nums[i]];
        }
        // 统计满足条件的方案
        for(int j = sum/2 - nums[i-1] + 1, s = (sum+1)/2; j < s; ++j) {
            ans += dp[j];
        }
    }
    
    return ans;
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);
    }
    printf("%" PRIdFAST64 "\n", solve());
    return 0;
}

import java.util.*;

public class Main {
    static final int MAX_N = 50;
    static int n;
    static int[] nums = new int[MAX_N];
    static long[] dp = new long[MAX_N * 30000 + 5];
    
    static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
    
    static long solve() {
        // 计算GCD并简化数组
        int sum = 0, g = nums[0];
        for(int i = 1; i < n; ++i) {
            g = gcd(g, nums[i]);
        }
        for(int i = 0; i < n; ++i) {
            nums[i] /= g;
            sum += nums[i];
        }
        
        // 排序
        Arrays.sort(nums, 0, n);
        
        // 初始化dp数组
        dp[0] = 1;
        
        // 特殊情况：最大值超过总和一半
        long ans = nums[n-1] > sum/2 ? 1 : 0;
        
        // 动态规划
        for(int i = n-1; i > 0; --i) {
            for(int j = (sum-1)/2; j >= nums[i]; --j) {
                dp[j] += dp[j - nums[i]];
            }
            for(int j = sum/2 - nums[i-1] + 1, s = (sum+1)/2; j < s; ++j) {
                ans += dp[j];
            }
        }
        
        return ans;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0; i < n; ++i) {
            nums[i] = sc.nextInt();
        }
        System.out.println(solve());
    }
}

def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)

def solve(n, nums):
    # 计算GCD并简化数组
    g = nums[0]
    for i in range(1, n):
        g = gcd(g, nums[i])
    
    nums = [x // g for x in nums]
    total_sum = sum(nums)
    nums.sort()
    
    # 初始化dp数组
    dp = [0] * (total_sum + 1)
    dp[0] = 1
    
    # 特殊情况：最大值超过总和一半
    ans = 1 if nums[-1] > total_sum // 2 else 0
    
    # 动态规划
    for i in range(n-1, 0, -1):
        for j in range((total_sum-1)//2, nums[i]-1, -1):
            dp[j] += dp[j - nums[i]]
        
        start = total_sum//2 - nums[i-1] + 1
        end = (total_sum+1)//2
        for j in range(start, end):
            ans += dp[j]
    
    return ans

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    print(solve(n, nums))

if __name__ == "__main__":
    main()