算法

(动态规划) $O(n^4)$

注意到，“选择的 $m$ 个数的平均值为整数” 等价于 “选择的 $m$ 个数的累加和是 $m$ 的倍数”

记 dp[i][j][k] 表示到 $a_i$ 为止，选择的 $j$ 个数的累加和 $\% \, m = k$ 的方案数
然后遍历 $m = 1, 2, 3, \cdots, n$，分别求出所有的 $dp[i][j][k]$

最后的答案为 $\sum\limits_{m=1}^n dp[n][m][0]$

C++ 代码

#include <bits/extc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    mint ans;
    for (int m = 1; m <= n; ++m) {
        vector dp(m+1, vector<mint>(m));
        dp[0][0] = 1;
        rep(i, n) {
            for (int j = m-1; j >= 0; --j) {
                rep(k, m) {
                    dp[j+1][(k+a[i])%m] += dp[j][k];
                }
            }
        }
        ans += dp[m][0];
    }

    cout << ans.val() << '\n';

    return 0;
}