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

27 LCA模拟赛3T3 三等分的数组 题解

三等分的数组

题面

小 Y 有一个长度为 \(n\) 的数组,数组中的每个数都是一个 \(1 \sim m\) 之间的正整数。

小 Y 决定将这个数组分成若干个三元组:每个三元组要么由三个相同的数字组成,要么由三个连续的数字组成。换句话说,每个三元组的形式要么是 \((x, x, x)\),要么是 \((x, x + 1, x + 2)\),其中 \(x\) 是一个正整数。

求出将数组分成三元组的方案数,答案对 \(10^9 + 7\) 取模。

\(1 \le n \le 5000,\ 1 \leq a_i \leq m \leq 5000\)

其中 \(n\)\(3\) 的倍数。

题解

我们可以直接考虑大小为 \(i\) 的所有整数而不是每个数字,这样显然更方便我们进行分组。

因为要考虑连续三个数分成一组的情况,所以我们要记录一下当前数字还剩多少以及上个数字还剩多少,从而转移到下一个数字。

\(f(i,j,k)\) 表示考虑了前 \(i\) 个数字,\(i - 2\) 以及更小的数字保证没有剩余,\(i - 1\) 还剩 \(j\) 个,\(i\) 还剩 \(k\) 个的方案数。初始 \(f(1, 0, c_1) = 1\)

有转移:

\[\begin{align*} &f(i,j,k) \to f(i + 1, k - j, c_{i + 1} - j) \\ &f(i,j,k) \to f(i, j, k - 3) \end{align*} \]

这个状态数好像很大,为 \(O(n^3)\),但实际上远远到不了那么大,因为 \(\sum c_i = n\)

我们可以证明,其状态数不会超过 \(O(n^2)\)

\(A = \sum_{i \in odd} c_i,\ B = \sum_{i \in even},\ C = \sum_{i = 1}^{m - 1} c_i \times c_{i + 1}\),其中 \(C\) 即为我们的状态数。

不难发现 \(A \times B > C, A + B = n\)

由基本不等式可得 \(A + B \ge 2\sqrt{A \times B}\) ,所以 \(A \times B \le \frac {n^2} 4\)

所以时间复杂度和空间复杂度都是对的,空间可以用 vector 或者滚动数组。

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <vector>using namespace std;namespace michaele {typedef long long ll;const int N = 5e3 + 10;const int mod = 1e9 + 7;int n, m;int c[N];void solve () {cin >> n >> m;for (int i = 1; i <= n; i ++) {int x;cin >> x;c[x] ++;}vector <vector <vector <ll> > > f (m + 5, vector <vector <ll> > ());for (int i = 0; i <= m; i ++) {if (i) {f[i].resize (c[i - 1] + 5);for (int j = 0; j <= c[i - 1]; j ++) {f[i][j].resize (c[i] + 5);}} else {f[i].resize (10);}}f[1][0][c[1]] = 1;for (int i = 1; i < m; i ++) {for (int j = 0; j <= c[i - 1]; j ++) {for (int k = c[i]; k >= 0; k --) {auto now = f[i][j][k];if (k >= j && c[i + 1] >= j) {auto &nt = f[i + 1][k - j][c[i + 1] - j];nt += now;if (nt >= 1e18) {nt %= mod;}}if (k >= 3) {auto &nt = f[i][j][k - 3];nt += now;if (nt >= 1e18) {nt %= mod;}}}}}for (int k = c[m]; k >= 0; k --) {if (k >= 3) {f[m][0][k - 3] += f[m][0][k];if (f[m][0][k - 3] > 1e18) {f[m][0][k - 3] %= mod;}}}cout << f[m][0][0] % mod << endl;}}int main () {michaele :: solve ();return 0;
}
http://www.hskmm.com/?act=detail&tid=32354

相关文章:

  • 26 LCA模拟赛3T2 连边 题解
  • 28 S2模拟赛T2 开会council 题解
  • 25 LCA模拟赛3T1 ROI 2012马赛克 题解
  • 实验记录2025/10/14
  • 个人微信开发框架
  • 投资指标技术分析
  • linux源码编译python
  • uni-app x开发商城系统,Swiper 轮播图
  • 昂瑞微OM6651A:国产车规级蓝牙芯片的破局者
  • 2025年中央空调/锅炉房/机房运维服务厂家最新权威推荐榜:专业托管与维修外包一体化解决方案精选
  • 【终极解决方案】api-ms-win-core-path-l1-1-0.dll 缺失?Win7/Win10/Win11完整修复教程
  • 2025 年最新推荐分切机实力厂家权威榜单:覆盖全自动高速、铝箔、薄膜、高精度等机型,为软包装企业精选优质设备
  • 打破应用跳转流失困局,提升推广链接转化率
  • 性能测试进阶秘籍:如何用JMeter分布式压测挖掘系统极限潜
  • Codeforces Round 1058 (Div. 2) A~E
  • 2025 年生料带厂家最新推荐排行榜:解析优质品牌优势,涵盖新型、彩色、液态等多类型生料带厂家企业推荐
  • openresty开发lua-resty-openssl之对称加密解密 - liuxm
  • 哈希乱搞:CF1418G Three Occurrences
  • 2025 年废旧轮胎裂解加热生产厂家最新推荐榜单:优质企业专利技术、产能规模与口碑实力全景解析锂化工焚烧炉/氟化热风系统/煤化工热风炉厂家推荐
  • 悲伤 自卑 乖戾 独自哭泣 陪伴空虚 kill my memory 让我将痛苦全忘记
  • 日志 | 2025.10
  • 工程师的 “指尖实验室”!正点原子 LT1 电桥镊子深度测评:同价位竞品谁能打?
  • 【ACM出版|EI检索稳定】2025年AI驱动下:业务转型和数据科学创新国际学术会议(ICBTDS 2025)
  • 破解跨域监控难题:国标GB28181算法算力平台EasyGBS视频调阅技术在跨域安防监控中的核心应用
  • 2025 年电缆桥架源头厂家最新推荐排行榜:聚焦优质供应商核心竞争力,助力工程采购精准选型
  • 2025 年厂房出售公司服务推荐排行榜:珠三角/广州/深圳/东莞/佛山/珠海等城市优质厂房出售公司全面测评解析
  • 构建智能视觉中枢:国标GB28181算法算力平台EasyGBS的全域感知与播放方案
  • 别再乱排查了!Kafka 消息积压、重复、丢失,根源基本都是 Rebalance!
  • 2025年交通杯-爆破题wp
  • 挖象浏览器下载安装教程|支持淘宝、拼多多、抖音多平台账号分区管理