题解：P14360 [CSP-J 2025] 多边形 / polygon（目前仅有本题有民间数据）

给出

n

根小木棍的长度，从中任选若干根，求其拼成多边形的方案数。

1 \le n \le 5000, 1 \le V \le 5000

，其中

V

是小木棍长度的最大值。

正难则反。考虑从中任选若干根，不能拼成多边形的方案数。

考虑动态规划。先给小木棍长度升序排序。令

F_i(x)

为只考虑前

i

根木棍，其长度和恰好为

x

的方案数。显然

F_i(x) = F_{i - 1}(x- A_i) + C_i(x)

，其中

C_i(x)

表示前

i

根木棍中长度恰为

x

的个数。

最终答案即为

2^n - 1 - n - \binom{n}{2} - \sum\limits_{1 \le i \le n}\sum\limits_{1 \le x \le A_i}F_i(x)

。

时间复杂度

O(nV)

，空间复杂度

O(n)

。

代码

CPP

const i64 p = 998244353;
inline i64 mod(i64 x) { return (x % p + p) % p; }
inline i64 qpow(i64 a, i64 b) {
  i64 ret = 1;
  while (b) {
    if (b & 1) ret = mod(ret * a);
    a = mod(a * a);
    b >>= 1;
  }
  return ret;
}
void solve(i32 _) {
  i32 n;
  i64 ans = 0;
  std::cin >> n;
  std::vector<i32> a(n + 2, 0);
  for (i32 i = 1; i <= n; i++) std::cin >> a[i];
  std::sort(a.begin() + 1, a.begin() + n + 1);
  i32 V = a[n];
  std::vector<std::vector<i64>> f(2, std::vector<i64>(V + 2, 0));
  for (i32 i = 1; i <= n; i++) {
    for (i32 j = 1; j <= a[i]; j++) ans = mod(ans + f[1][j]);
    for (i32 j = V - a[i]; j >= 0; j--)
      f[1][j + a[i]] = mod(f[1][j + a[i]] + f[1][j] + f[0][j]);
    f[0][a[i]]++;
  }
  std::cout << mod(qpow(2, n) - 1 - n - mod(n * (n - 1) * qpow(2, p - 2)) - ans)
            << endl;
  return void();
}

题解：P14360 [CSP-J 2025] 多边形 / polygon（目前仅有本题有民间数据）

文章操作

相关推荐

评论

题解：P14360 [CSP-J 2025] 多边形 / polygon（目前仅有本题有民间数据）