Super League of Chinese College Students Algorithm Design 2021
Contest 10
August 19th, 2021
1 A. Pty loves sequence
如何不重不漏地统计好的序列？
设最大值 = k ，我们可以取最前的一个 [1, 2, &, k − 1, k] 子序列。
再考虑往它们之间的空插数，不难发现，要使该子序列是最前的，唯一的限制条件是：
对于 x − 1 和 x(1 ≤ x ≤ k) 之前那个空，里面不能有 x 。
特别的，最后一个空没有限制。
那么只需要枚举最后一个空的填的数的个数 i ，由挡板法可得填数方案是 k
i
∗(k −1)
n−k−i
∗
n−k−i+k−1
k−1
第一问的答案 Ans =
P
n
k=1
P
n−k
i=0
k
i
∗ (k −1)
n−k−i
∗
n−i−1
k−1
第二问的做法可以由第一问得到。
比较显然的一个结论：
当 k 固定时， 1..k 在好的序列中的出现次数是相同的。
简略证明：
第一问的做法中，当 k 固定时，限制为第 i 个空不能填 i ，最后一个空随意。
因为对 1..k 每个元素的限制是一样的，所以 1..k 本质相同，因此出现次数应当相同。
所以枚举 k ，使 ans[1..k]+ = (
P
n−k
i=0
k
i
∗ (k −1)
n−k−i
∗
n−i−1
k−1
) ∗
n
k
。
最后的问题在于本题的模数不是质数，所以没有逆元，因此需要把
n
k
化进式子里。
观察式子，不难得到：
当 i > 0 时，把 k
i
变成 k
i−1
即可。
当 i = 0 时，把
n−1
k−1
∗
n
k
变成
n
k
即可。
那么式子里只用到了幂和组合数，组合数可以杨辉三角预处理，所以模数不需要是质数。
时间复杂度： O(n
2
)
事实上当 p = 998244353 时，这题可以做到： O(n
√
n log n) ，需要用到多项式多点求值。
因为该做法常数颇大，且代码较长，不适合于ACM比赛，所以善良的出题人并没有放这个版本。
1
下载后可阅读完整内容，剩余6页未读，立即下载
梁肖松
- 粉丝: 29
- 资源: 300
我的内容管理
展开
最新资源
- 十种常见电感线圈电感量计算公式详解
- 军用车辆：CAN总线的集成与优势
- CAN总线在汽车智能换档系统中的作用与实现
- CAN总线数据超载问题及解决策略
- 汽车车身系统CAN总线设计与应用
- SAP企业需求深度剖析：财务会计与供应链的关键流程与改进策略
- CAN总线在发动机电控系统中的通信设计实践
- Spring与iBATIS整合：快速开发与比较分析
- CAN总线驱动的整车管理系统硬件设计详解
- CAN总线通讯智能节点设计与实现
- DSP实现电动汽车CAN总线通讯技术
- CAN协议网关设计：自动位速率检测与互连
- Xcode免证书调试iPad程序开发指南
- 分布式数据库查询优化算法探讨
- Win7安装VC++6.0完全指南：解决兼容性与Office冲突
- MFC实现学生信息管理系统：登录与数据库操作
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
