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

模拟赛T4 分析

题目概述

随机 \(2n\) 个数,值域为 \([0,m]\),求前 \(n\) 个数比后 \(n\) 个数大的概率(对质数 \(P\) 取模),其中 \(10^8\leq P\leq 10^9\)

数据范围:\(1\leq n,m,T\leq 2000\)

分析

好好玩。

显然可以转化为计数题目。

赛时想了一个 \(\mathcal{O}(Tn^2m)\) 做法。

首先我们不难想到设 \(f_{i,j}\) 表示前 \(i\) 个数和为 \(j\) 的方案。转移是简单的,求答案也是简单的:

\[ans=\sum_j\sum_{k<j} f_{n,j}\times f_{n,k} \]

两者都可以用前缀和优化。

正解肯定不是这么乱搞的。

首先可以分成三种情况:

  • 前面 \(n\) 个小于后面 \(n\) 个。
  • 前面 \(n\) 个等于后面 \(n\) 个。
  • 前面 \(n\) 个大于后面 \(n\) 个。

我们发现第一个和第三个其实是一样的。

于是我们的答案就是总共方案减去等于的方案再除以 \(2\)

我们发现等于的方案很难去做,很难刻画。

考虑做一些精妙的转变:

将后 \(n\) 个数取反,相当于前面的数的值域为 \([0,m]\),后面的为 \([-m,0]\),等于就变成了相加为 \(0\)

再将后 \(n\) 个数每个数加上 \(m\),相当于前面的数的值域为 \([0,m]\),后面的数也是,相加为 \(0\) 就变成了相加为 \(nm\)

我们发现这个是好做的,至于怎么想到的,确实很难,不过灵光一现还是有可能的。

我们现在假设去掉这个限制(经典容斥片头曲),那么相当于在 \(2n\) 个非负数中得到的和为 \(nm\) 的方案。

http://www.hskmm.com/?act=detail&tid=34483

相关文章:

  • ubuntu系统中containerd的cni网络配置
  • 十月阅读笔记
  • #20232408 2025-2026-1 《网络与系统攻防技术》实验二实验报告 - 20232408
  • 题解:P2672 [NOIP 2015 普及组] 推销员
  • 一文读懂Schnorr签名
  • 如何选择合适的SAP实施公司?3步锁定靠谱的SAP服务商
  • CSP-S2024
  • 10/19
  • 论DCT和IDCT的重要性,汇编SIMD版第一,此贴第二,就是这么狂 :-)
  • 这些SAP实施公司哪家强?国内比较好的SAP实施商推荐
  • 25秋周总结5
  • UML图
  • 博士研究文档管理技术指南
  • 题解:P12128 [蓝桥杯 2024 省 B 第二场] 质数变革
  • 题解:P12003 在小小的奶龙山里面挖呀挖呀挖(加强版)
  • apisix升级完整流程
  • 10.11-10.18 一周总结
  • 10/19/2025 一周总结
  • 如何生成逼真的合成表格数据:独立采样与关联建模方法对比
  • winform+Task+async
  • AI元人文:跨学科视野下的人工智能伦理新范式
  • Rust 开发最佳实践(Rustlang Best Practices)
  • Why dont Japanese people reply to messages
  • 20232301郑好 实验二 后门原理与实践
  • 2025年复合钢丝网厂家推荐排行榜,昆山高精密网版,复合钢丝网公司精选!
  • 20232322 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 消防局的设立
  • Python 潮流周刊#73:让我们对 PyPI 温柔一点,好吗?
  • 2025 年中国超声波流量计行业品牌全景分析报告:十大高性能品牌技术、性能与市场优势深度解析
  • 2025年精密弹簧厂家推荐排行榜,微型精密弹簧,不锈钢精密弹簧,高弹性精密弹簧公司推荐!