CSP-J2025T4题解

是时候该开垦皇帝荒地了

题意

有 $n$ 根小木棍，长度分别为 $a_{1} , a_{2} , ⋯ , a_{n}$ 。从这 $n$ 根木棍中选出 $m$ 根 ( $m≥3$ )，它们能拼成一个多边形当且仅当所有选出木棍的长度之和大于最长木棍长度的两倍。 要求计算出有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形，答案对 $998244353$ 取模

解析

不妨将所有给定木棍根据其长度 $a_{i}$ 排序，假设第 $i$ 根木棍被选择且其长度最大，则需要在前 $i-1$ 根木棍中选取部分，使选择的木棍长度和大于 $a_{i}$ ，这个无法直接求，不过我们可以考虑求其补集。即在前 $i-1$ 根木棍中选取部分，使其长度和小于等于 $a_{i}$ 。 这一转换后的问题显然可以用动态规划处理，记 $dp_{i,j}$ 表示前 $i$ 根木棍中选取若干，使其长度和为 $j$ 的方案数，有 $dp_{i,j} = dp_{i - 1 , j} + dp_{i - 1 , j - a_{i}}$ 注意 $a_{i} > j$ 时，后一项视为0.最后用所用的所有选取方案数减去 $2^n$ 减去不合法的部分即可

答案

#include <bits/stdc++.h>
#define ll long long
#define MN 5000
#define N 5010
#define M 998244353
using namespace std;

ll n, m, num[N], dp[N];

inline void Add(ll &u, ll v) { u = (u + v) % M; } // u+=v，再取模
inline ll po(ll u, ll v)                          // 乘法快速幂，计算 u^v
{
    ll res = 1;
    for (; v;)
    {
        if (v & 1)
            res = res * u % M;
        u = u * u % M;
        v >>= 1;
    }
    return res;
}

int main()
{
    dp[0] = 1;
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &num[i]);
    sort(num + 1, num + n + 1);

    ll ans = po(2, n) - 1;       // 总方案数
    for (int i = 1; i <= n; i++) // 枚举最长木棍 ai
    {
        for (int j = 0; j <= num[i]; j++)
            Add(ans, M - dp[j]); // 去掉此时的不合法方案
        for (int j = MN; j >= num[i]; j--)
            Add(dp[j], dp[j - num[i]]); // 状态转移
    }
    cout << ans;
}