P14360 [CSP-J 2025] 多边形 / polygon（民间数据）

_GIGjqw12_ · 2025-11-01 16:08:59 · 题解

题意理解

• 有 n 根木棍，长度分别为 a₁, a₂, ..., aₙ。
• 要选出若干根（至少 3 根）拼成多边形。
• 多边形条件：设选出的木棍长度为 l₁, l₂, ..., lₘ (m ≥ 3)则总长度 > 2 × 最大长度。
• 问有多少种选择木棍的方案（不同下标集合算不同方案）。

• 答案对 998244353 取模。 代码如下：

  #include <iostream>
  #include <algorithm>
  #include <vector>
  using namespace std;
  const int M=998244353;
  int main() {
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
      cin>>a[i];
  }
  sort(a.begin(), a.end());
  long long l_s=1;
  for (int i=0;i<n;i++) {
      l_s=(l_s*2)%M;
  }
  long long d_s=(l_s-1-n-(long long)n*(n-1)/2)%M;
  if (d_s<0)d_s+=M;
  
  int x_s=a.back()*2; 
  vector<long long> dp(x_s+1,0);
  dp[0] = 1;
  
  long long d_c=0;
  
  for (int i=0;i<n;i++){
      long long m_l = 0;
      for (int s=0;s<=a[i];s++) {
         m_l= (m_l+dp[s])%M;
      }
      if (i >= 2) { 
          long long d_f=(m_l-1-i)%M;
          if (d_f<0)d_f+=M;
          d_c= (d_c+d_f)%M;
      }
      for (int s = x_s; s>=a[i];s--) {
          dp[s]=(dp[s] + dp[s-a[i]])%M;
      }
  }
  long long ans = (d_s-d_c)%M;
  if (ans<0) ans+=M;
  cout <<ans<<endl;
  
  return 0;
  }