1 条题解
-
0
题目分析
算法 1
我会暴力!
枚举 的全排列,单次 查询是否符合条件,累加即可。
期望得分 5 分。
算法 2
期望得分 40 分。
算法 3
我会先猜结论然后证明!
【结论】 令下标数列 表示所有 ,则答案为 。
【证明】 令 表示 的答案。
设【结论】对 成立,且存在 为它的符合条件的排列,则对于 :
- 若 ,则显然只有在 末尾加上 符合要求,即 。
- 若 ,考虑对于 ,以下变换方法是唯一的:将 都加上 ,然后在末尾加上 。
这样的 共有 种,即 。
容易发现【结论】对 成立(其中 且对结果没有影响),数学归纳可得,【结论】对任意 成立。
时间复杂度为 。
期望得分 100 分。
- 1
信息
- ID
- 174
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者