1 条题解
-
0
题目分析
本题考察了动态规划的相关知识。
10pts
表示能否得到 的状态,枚举下一个取模的数进行转移。
+20pts
注意到只会取模 , 枚举并去重即可。
+50pts
因为 ,思考该序列进行若干次操作以后的形态。
首先注意到给定的参数 一定递减,否则无意义。
我们以 为例,模拟 的变化过程
时,。
加入 时,。
加入 时,。
这个过程并不直观,我们把整个过程倒过来。
时,。
时,。
时,。
可以发现从小到大加入所有正整数 ,加入该数字时即为将第 位修改为 ,然后变成一个 为循环节的数列。
从以上性质倒退,我们可以断言,以下 序列可以构造得到的充要条件为:
- 存在一个正整数 ,对于 都有 且 。
- 对于 ,有 ,且 或 。
因为我们可以取每个 处加入到 这一操作集合,即可构造出以上方案。
容易发现此时 一定唯一,枚举 进行计数。
100pts
假设最终序列为 。
将所有 从小到大进行排序,枚举 的值进行DP, 表示将 修改为 ,此时 不同的方案数,转移时要求 且 ,直接 DP 即可,这样可能会算重,在此基础上强制要求 在 序列中出现即可,因此用 表示 是否出现,且 的方案数。
- 1
信息
- ID
- 171
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者