cf523C


转移自老blog

cf523C

链接

题意

        给你一个n( (1≤𝑛≤100000)个数的数列,让你构造一个序列,保证每个位置的数字能整除这个位置的下标。问有多少个子序列满足这种做法。

题解

        dp[i][j]代表前i个数,构成长度为j的数列的方案数
        dp[i][j] <--- dp[i-1][j-1]  j|a[i] 预处理每个数的因子即可
        然后发现若从大到小枚举因子则第一维可以优化掉,

文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录