题目描述

难度分:$1213$

输入$n(1 \leq n \leq 100)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

如果一个非空子序列的平均值是整数，那么称其为漂亮的。

输出$a$的漂亮子序列的个数，模$998244353$。

注：子序列不一定连续。

输入样例$1$

3
2 6 2

输出样例$1$

6

输入样例$2$

5
5 5 5 5 5

输出样例$2$

31

算法

动态规划

这个题没有想到很好的办法来做，只想到一个$O(n^4)$的DP做法，枚举序列长度，每个长度都进行DP。

状态定义

$dp[i][rest][s]$表示从前$i$个元素中选择$rest$个数字，在和为$s$的情况下能够得到的平均值为整数的方案数。其实可以发现，一边计算序列和$s$，一边对长度取模即可，如果选择满了$rest$个元素时满足$s=0$，就说明序列总和能够被其长度除尽，也就说明平均数是整数。

状态转移

类似01背包，当前元素$a[i]$可以选也可以不选，状态转移方程如下

$dp[i][rest][s]=dp[i+1][rest][s]$

如果还能取$a[i]$，就有

$dp[i][rest][s]=dp[i+1][rest-a[i]][(s+a[i]) \% t]$，其中$t$为此时枚举的序列长度。

复杂度分析

时间复杂度

枚举的序列长度有$O(n)$规模，每次动态规划有$O(n^3)$个状态，状态转移的时间复杂度为$O(1)$，因此整体的时间复杂度为$O(n^4)$。

空间复杂度

额外空间就是开辟的DP数组，规模为状态数量$O(n^3)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110, MOD = 998244353;
int n, t, a[N], dp[N][N][N];

int dfs(int i, int rest, int s) {
    if(i > n) {
        return rest == 0 && s == 0? 1: 0;
    }
    int& v = dp[i][rest][s];
    if(v != -1) return v;
    int res = dfs(i + 1, rest, s);
    if(rest >= 1) res = (res + dfs(i + 1, rest - 1, (s + a[i])%t)) % MOD;
    return v = res;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int ans = n;
    for(t = 2; t <= n; t++) {
        memset(dp, -1, sizeof(dp));
        ans = (ans + dfs(1, t, 0)) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}