C++ 解法, 执行用时: 32ms, 内存消耗: 6660KB, 提交时间: 2020-10-28

#include <bits/stdc++.h>
#define MAX_N 50
using namespace std;
typedef int_fast64_t INT64;
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() {
    int sum = 0, g = *nums;
    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) {
        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;
}

C++ 解法, 执行用时: 33ms, 内存消耗: 6604KB, 提交时间: 2020-10-29

#include <bits/stdc++.h>
#define MAX_N 50
using namespace std;
typedef int_fast64_t INT64;
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() {
    int sum = 0, g = *nums;
    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) {
        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;
}