当前位置: 首页 > news >正文

题解:CF2125E Sets of Complementary Sums

题目:

\(m\)\(m\) 任取)个正整数组成的 \(a\) 数组按照题目操作可构造的长度为 \(n\) 值域为 \([1,x]\) 的集合数量。
题目操作为:\(s=\sum_{i=1}^m a_i\),把 \(s-a_i\) 插入集合。

推点性质

1

集合有无序性,令集合内升序排序,可以代表这个集合。
\(a\) 也有无序性,所以也升序排序。(具体的 \(a_i\le a_{i+1}\)

2

考虑增量:
如果新加入的 \(a_i\) 之前出现过,则不会增加集合元素,只会让集合整体加 \(a_i\)
如果没出现过,则会让集合整体加 \(a_i\) 后加入 \((\sum_{j=1}^i a_j) -a_i\)

3

首先看到 \(s-a_i\) 容易想到差分,发现:
\(a\) 不重,那么 \(a\) 的差分数组和集合的差分数组是一样的。
\(a\) 有重,\(a\) 去完重后的差分数组和集合的差分数组还是一样的,因为重的 \(a_i\) 只会影响 \(s\)。所以下面我们均维护去重后的 \(a\),而重复的 \(a_i\) 会体现为全局加。

4

构造 \(a_1=1\)\(a\),集合最大值为 \(s-1\),对应的合法原数组数量为 \(x-(s-1)+1\)。(同时也可知 \(s\le x+1\) 的范围。)

于是有个暴力 DP:
\(f_{i,j,k}\):构造 \(a_1=1,\left | a \right |=i,s=j,a_i=k\) 的方案数。
转移 \(O(nx^3)\)。(实际上判掉无解是 \(O(\sqrt x x^3)\)

5

思考如何优化性质 \(4\) 的 DP,考虑去掉 \(k\) 这一维,我们定义两种操作:

  1. \(a\) 序列前拼接 \(1\)
  2. \(a\) 序列整体 \(+1\)

我们发现这样很好维护递增的条件了,并且我们也不用枚举新拼接的数,因为我们可以类似完全背包地考虑到每个新拼接的数。

\(f_{i,j,0/1}\)\(\left | a \right | =i,s=j\)\(a_1\) 是否有 \(1\)

\[f_{i,j,1}=f_{i-1,j-1,0} \]

\[f_{i,j,0}=f_{i,j-i,0}+f_{i,j-i,1} \]

6

由于 \(s\le x+1\) 且我们 DP 的是无重复元素的 \(a\),所以 \(\frac{(1+n)n}{2}\le x+1\) 时,\(f_n\) 才会有值。
判完无解复杂度为 \(O(\sqrt x x)\)

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x;
}
void xie(int x,int shen=0)
{if(!x){if(!shen) putchar('0');return ;}xie(x/10,1);putchar('0'+x%10);
}
const int QAQ=2e5+7,mo=998244353;
int t,n,x,dp[QAQ][2];
signed main()
{t=read();for(int i1=1;i1<=t;i1++){n=read(),x=read();if(n==1) {xie(x),putchar('\n');continue;}if(n*(n-1)/2>x+1) {puts("0");continue;}for(int i=0;i<=x+1;i++) dp[i][0]=dp[i][1]=0;dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=x+1;j++) dp[j][1]=dp[j-1][0];for(int j=0;j<=x+1;j++)if(j<i) dp[j][0]=0;else dp[j][0]=(dp[j-i][0]+dp[j-i][1])%mo;}int ans=0;for(int i=1;i<=x+1;i++) ans=(ans+dp[i][1]*(x-i+2)%mo)%mo;xie(ans);putchar('\n');}return 0;
}
http://www.hskmm.com/?act=detail&tid=21114

相关文章:

  • 929
  • ManySpeech —— 使用 C# 开发人工智能语音应用
  • 20250929
  • 驱动基础知识速览(迅为RK3568文档)
  • 学习笔记-析合树
  • CSPJ2025模拟赛
  • java代码审计-Shiro认证授权
  • CF868F题解
  • ThinkPHP反序列化分析
  • AT_iroha2019_day4_l 题解
  • AT_abc290_f 题解
  • 一张图读懂绿电直连系统架构 - 智慧园区
  • P5469 [NOI2019] 机器人 题解
  • 题解:P14080 [GESP202509 八级] 最小生成树
  • 实用指南:Spring Cloud Gateway 实战:全局过滤器日志统计与 Prometheus + Grafana 接口耗时监控
  • GTSAM 中自定义因子(Custom Factor)的详解和实战示例 - 指南
  • AtCoder AGC073 A 题解
  • CF506C Mr. Kitayuta vs. Bamboos 51nod1457 小K vs. 竹子 题目分析
  • 北京 意大利 硕士学签/D签 vfs代办 材料清单
  • temp
  • 我有园子了
  • 使用 Jenkins 的流水线方案实施 CI/CD
  • 加密的病例单
  • 详细介绍:视频融合平台EasyCVR构筑智慧交通可视化管理与智能决策中枢
  • docker 在x86上build arm 镜像
  • 9.29软工
  • 不一样的.NET烟火,基于Roslyn的开源代码生成器
  • 复刻江协旋钮控制模块
  • 告别硬编码!5个让Web自动化脚本更稳定的定位策略
  • 从零开始,使用Idea工具搭建一个springboot项目