1 条题解

  • 0
    @ 2026-11-15 19:08:58

    题目分析

    本题考察了动态规划的相关知识。

    10pts

    f[i][j]f[i][j] 表示能否得到 a1=i,a2=ja_1=i,a_2=j 的状态,枚举下一个取模的数进行转移。

    +20pts

    注意到只会取模 x∈[1,20]x \in [1,20],2202^{20} 枚举并去重即可。

    +50pts

    因为 ai=ia_i=i,思考该序列进行若干次操作以后的形态。

    首先注意到给定的参数 xx 一定递减,否则无意义。

    我们以 x=7,5,3x=7,5,3 为例,模拟 aia_i 的变化过程

    x=7x=7 时,a=1,2,3,4,5,6,0,1,2,3,4,5,6,0,…a=1,2,3,4,5,6,0,1,2,3,4,5,6,0,…。

    加入 x=5x=5 时,a=1,2,3,4,0,1,0,1,2,3,4,0,1,0,…a=1,2,3,4,0,1,0,1,2,3,4,0,1,0,…。

    加入 x=3x=3 时,a=1,2,0,1,0,1,0,1,2,0,1,0,1,0a=1,2,0,1,0,1,0,1,2,0,1,0,1,0。

    这个过程并不直观,我们把整个过程倒过来。

    x=3x=3 时,a=1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,...a=1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,...。

    x=3,5x=3,5 时,a=1,2,0,1,0,1,2,0,1,0,...a=1,2,0,1,0,1,2,0,1,0,...。

    x=3,5,7x=3,5,7 时,a=1,2,0,1,0,1,0,1,2,0,1,0,1,0...a=1,2,0,1,0,1,0,1,2,0,1,0,1,0...​。

    可以发现从小到大加入所有正整数 xix_i,加入该数字时即为将第 xix_i 位修改为 00,然后变成一个 xix_i 为循环节的数列。

    从以上性质倒退,我们可以断言,以下 aia_i 序列可以构造得到的充要条件为:

    1. 存在一个正整数 xx,对于 1≤i<x1 \leq i < x 都有 ai=ia_i=i 且 ax=0a_x=0​。
    2. 对于 i>xi >x,有 ai<xa_i < x,且 ai=0a_i=0 或 ai=ai−1+1a_i=a_{i-1}+1。

    因为我们可以取每个 ai=0a_i=0 处加入到 xx 这一操作集合,即可构造出以上方案。

    容易发现此时 xx 一定唯一,枚举 xx 进行计数。

    100pts

    假设最终序列为 bb。

    将所有 aa 从小到大进行排序,枚举 xx 的值进行DP,f[i][j]f[i][j] 表示将 aia_i 修改为 jj,此时 a1,a2,…,aia_1,a_2,…,a_i 不同的方案数,转移时要求 b[i]<xb[i] < x 且 b[i+1]−b[i]≤a[i+1]−a[i]b[i+1]-b[i] \leq a[i+1]-a[i],直接 DP 即可,这样可能会算重,在此基础上强制要求 x−1x-1 在 bb 序列中出现即可,因此用 f[0/1][i][j]f[0/1][i][j] 表示 x−1x-1 是否出现,且 bi=jb_i=j 的方案数。

    • 1

    信息

    ID
    171
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者