I Hate Non-integer Number

q0y1 · 2023-05-17 15:50:00 · 个人记录

I Hate Non-integer Number

题意

给定一个长度为 N 的正整数序列 A = ( a_1 \dots a_n)。有 (2n-1) 种方法选择 A 中一个或更多的元素。有多少种选择方法使得选出的元素的平均数为整数？答案对 998244353 取模。

思路

dp，可以看作是一个子集搜索，所以可以定义状态为：(x, u, sum) 表示 x 个数，已经选了 u 个，他们的余数为 sum 时的总方案数。由于可以有很多种子集的长度，所以枚举长度在搜索即可。

代码

#include <iostream>

using namespace std;
using ll = long long;

const int MaxN = 110, mod = 998244353;

int f[MaxN][MaxN][MaxN][MaxN], a[MaxN], n, y, ans;

int DFS(int x, int u, int sum) {
  if (x == n + 1) {
    return !sum && u == y;
  }
  if (u > y) {
    return 0;
  }
  if (f[y][x][u][sum] != -1) {
    return f[y][x][u][sum];
  }
  return f[y][x][u][sum] = (DFS(x + 1, u + 1, (sum + a[x] % y) % y) + DFS(x + 1, u, sum)) % mod;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (y = 1; y <= n; y++) {
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
          f[y][i][j][k] = -1;
        }
      }
    }
    ans = (ans + DFS(1, 0, 0)) % mod;
  }
  cout << ans << endl;
  return 0;
}