专栏文章

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

__GIGjqw12_
P14360题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minfp244
此快照首次捕获于
2025/12/02 01:39
3 个月前
此快照最后确认于
2025/12/02 01:39
3 个月前
查看原文

题意理解

  • 有 nn 根木棍，长度分别为 a1,a2,...,ana₁, a₂, ..., aₙ。
  • 要选出若干根（至少 33 根）拼成多边形。
  • 多边形条件：设选出的木棍长度为 l1,l2,...,lm(m≥3)l₁, l₂, ..., lₘ (m ≥ 3)则总长度 >2×> 2 × 最大长度。
  • 问有多少种选择木棍的方案（不同下标集合算不同方案）。
  • 答案对 998244353 取模。 代码如下：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...