nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cf523C

链接

https://codeforc.es/contest/1061/problem/C

题意

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

题解

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